Introducción al algoritmo BFS
Para acceder y administrar los datos de manera eficiente, se pueden almacenar y organizar en un formato especial conocido como estructura de datos. Hay muchas estructuras de datos como Pila, Array, Lista enlazada, Colas, Árboles y Gráficos, etc. En estructuras de datos lineales, como Pila, Array, Lista enlazada y Cola, los datos se organizan en orden lineal mientras que, en estructuras de datos lineales como árboles y gráficos, los datos se organizan jerárquicamente, no en una secuencia. El gráfico es una estructura de datos no lineal que tiene nodos y aristas. Los nodos en Graph también pueden denominarse vértices que son finitos en número y los bordes son las líneas de conexión entre dos nodos.
En el gráfico anterior, los vértices se pueden representar como V = (A, B, C, D, E) y los bordes se pueden definir como
E = (AB, AC, CD, BE)
¿Qué es el algoritmo BFS?
Generalmente hay dos algoritmos que se utilizan para atravesar un gráfico. Son algoritmos BFS (Breadth-First Search) y DFS (Depth First Search). El recorrido del gráfico es visitar exactamente una vez cada vértice o nodo y borde, en un orden bien definido. Además, es muy importante hacer un seguimiento de los vértices que han sido visitados para que el mismo vértice no se atraviese dos veces. En el algoritmo Breath First Search, el recorrido comienza desde un nodo seleccionado o un nodo fuente y el recorrido continúa a través de los nodos directamente conectados al nodo fuente. En términos más simples, en el algoritmo BFS, primero se debe mover horizontalmente y atravesar la capa actual, luego se debe mover a la siguiente capa.
¿Cómo funciona el algoritmo BFS?
Tomemos el ejemplo del siguiente gráfico.
La tarea importante en cuestión es encontrar la ruta más corta en un gráfico mientras recorre los nodos. Cuando atravesamos un gráfico, el vértice pasa del estado no descubierto al estado descubierto y finalmente se descubre por completo. Cabe señalar que es posible quedarse atascado en algún momento mientras se atraviesa un gráfico y se puede visitar un nodo dos veces. Por lo tanto, podemos emplear un método para marcar los nodos después de que cambie el estado de no ser descubierto a ser completamente descubierto.
Podemos ver en la imagen a continuación que los nodos se pueden marcar en los gráficos a medida que se descubren completamente al marcarlos con negro. Podemos comenzar en el nodo de origen y, a medida que avanza el recorrido a través de cada nodo, se pueden marcar para identificarlos.
El recorrido comienza desde un vértice y luego viaja a los bordes salientes. Cuando un borde va a un vértice no descubierto, se marca como descubierto. Pero cuando un borde va a un vértice completamente descubierto o descubierto, se ignora.
Para un gráfico dirigido, cada borde se visita una vez y para un gráfico no dirigido, se visita dos veces, es decir, una vez mientras se visita cada nodo. El algoritmo a utilizar se decide sobre la base de cómo se almacenan los vértices descubiertos. En el algoritmo BFS, la cola se usa donde se descubre primero el vértice más antiguo y luego se propaga a través de las capas desde el vértice inicial.
Se realizan pasos para un algoritmo BFS
Los siguientes pasos se realizan para un algoritmo BFS.
- En un gráfico dado, comencemos desde un vértice, es decir, en el diagrama anterior es el nodo 0. El nivel, en el que está presente este vértice, se puede denotar como Capa 0.
- El siguiente paso es encontrar todos los otros vértices adyacentes al vértice inicial, es decir, el nodo 0 o al que se puede acceder inmediatamente desde él. Luego podemos marcar estos vértices adyacentes para que estén presentes en la Capa 1.
- Es posible llegar al mismo vértice debido a un bucle en el gráfico. Entonces, deberíamos viajar solo a aquellos vértices que deberían estar presentes en la misma capa.
- A continuación, se marca el vértice principal del vértice actual en el que estamos. Lo mismo se realizará para todos los vértices en la capa 1.
- Luego, el siguiente paso es encontrar todos esos vértices que están a un solo borde de todos los vértices que están en la Capa 1. Este nuevo conjunto de vértices estará en la Capa 2.
- El proceso anterior se repite hasta que se atraviesen todos los nodos.
Ejemplo:
Tomemos el ejemplo del siguiente gráfico y comprendamos cómo funciona el algoritmo BFS. En general, en un algoritmo BFS, se usa una cola para poner en cola los nodos mientras los atraviesa.
En el gráfico anterior, primero se debe visitar el nodo 0 y este nodo se pone en cola a la cola siguiente:
Después de visitar el nodo 0, el nodo vecino de 0, 1 y 2 se pone en cola. La cola se puede representar de la siguiente manera: 
Luego se visitará el primer nodo de la cola que es 2. Después de visitar el nodo 2, la cola se puede representar de la siguiente manera:
Después de visitar el nodo 2, 5 se pondrá en cola y, dado que no hay nodos vecinos no visitados para el nodo 5, aunque 5 está en cola pero no se visitará dos veces.
A continuación, el primer nodo de la cola es 1, que se visitará. Los nodos vecinos 3 y 4 están en cola. La cola se representa a continuación
Luego, el primer nodo en la cola es 5, y para este nodo, no hay más nodos vecinos no visitados. Lo mismo ocurre con los nodos 3 y 4 para los cuales no hay más nodos vecinos no visitados también.
Entonces, todos los nodos se atraviesan y, finalmente, la cola se vacía.
Conclusión
Algoritmo de búsqueda de amplitud viene con algunas grandes ventajas para recomendarlo. Una de las muchas aplicaciones del algoritmo BFS es calcular la ruta más corta. Además, se usa en redes para encontrar nodos vecinos y se puede encontrar en sitios de redes sociales, difusión de redes y recolección de basura. Los usuarios deben comprender el requisito y el patrón de datos para usarlo para un mejor rendimiento.
Artículos recomendados
Esta ha sido una guía del algoritmo BFS. Aquí discutimos el concepto, el trabajo, los pasos y el ejemplo de rendimiento en el algoritmo BFS. También puede consultar nuestros otros artículos sugeridos para obtener más información:
- ¿Qué es un algoritmo codicioso?
- Algoritmo de trazado de rayos
- Algoritmo de firma digital
- ¿Qué es la hibernación de Java?
- Criptografía de firma digital
- BFS VS DFS | Las 6 principales diferencias con la infografía