Estructura de datos: primer recorrido en amplitud
El algoritmo Breadth First Search (BFS) atraviesa un gráfico en un movimiento de amplitud y utiliza una cola para recordar obtener el siguiente vértice para iniciar una búsqueda, cuando se produce un callejón sin salida en cualquier iteración.
Como en el ejemplo anterior, el algoritmo BFS atraviesa de A a B a E a F primero, luego a C y G por último a D. Emplea las siguientes reglas.
Rule 1- Visite el vértice adyacente no visitado. Márcalo como visitado. Muéstralo. Insértelo en una cola.
Rule 2 - Si no se encuentra ningún vértice adyacente, elimine el primer vértice de la cola.
Rule 3 - Repita la Regla 1 y la Regla 2 hasta que la cola esté vacía.
| Paso | El recorrido | Descripción |
|---|---|---|
| 1 |  |
Inicializa la cola. |
| 2 |  |
Empezamos visitando S (nodo inicial) y márquelo como visitado. |
| 3 |  |
Luego vemos un nodo adyacente no visitado de S. En este ejemplo, tenemos tres nodos pero elegimos alfabéticamenteA, márquelo como visitado y colóquelo. |
| 4 |  |
A continuación, el nodo adyacente no visitado de S es B. Lo marcamos como visitado y lo ponemos en cola. |
| 5 |  |
A continuación, el nodo adyacente no visitado de S es C. Lo marcamos como visitado y lo ponemos en cola. |
| 6 |  |
Ahora, Squeda sin nodos adyacentes no visitados. Entonces, sacamos de la cola y encontramosA. |
| 7 |  |
Desde A tenemos Dcomo nodo adyacente no visitado. Lo marcamos como visitado y lo ponemos en cola. |
En esta etapa, nos quedamos sin nodos sin marcar (no visitados). Pero según el algoritmo, seguimos eliminando la cola para obtener todos los nodos no visitados. Cuando la cola se vacía, el programa termina.
La implementación de este algoritmo en lenguaje de programación C se puede ver aquí .