El algoritmo Breadth First Search se implementó utilizando la estructura de datos de la cola. Un orden posible para visitar los Nodes del siguiente gráfico es
(A) MNOPQR
(B) NQMPOR
(C) QMNPRO
(D) QMNPOR
Respuesta: (C)
Explicación: La búsqueda primero en ancho visita primero el «ancho», es decir, si es visitando un Node, luego de visitar ese Node, visitará los Nodes vecinos (hijos) primero antes de pasar a los vecinos del siguiente nivel.
Veamos cómo.
Inicialmente: si BFS comienza en el Node Q, primero visita Q y pone Q en la cola.
Entonces, Queue contiene: Q.
Y, el orden de visita todavía es: Q.
Ahora quita Q y explora sus vecinos, que son {M,N,P}. Comprueba aquellos vecinos de Q que aún no han sido visitados, luego los visita y los pone en Cola (para que luego sus vecinos puedan ser visitados).
Ahora, estos vecinos pueden visitarse y ponerse en cola en cualquier orden (depende de la implementación).
Supongamos que visita y los pone en la cola en el orden (MNP) con M en la parte DELANTERA y P en la PARTE POSTERIOR.
Entonces, Orden de visita: QMNP.
Ahora, busca la siguiente entrada en Queue. Como Queue sigue el principio FIFO, M se elimina de la cola.
La cola contiene: (NP)
Explora M, encuentra sus vecinos { N, Q, R }, pero antes de visitarlos comprueba si estos han sido visitados anteriormente, solo visitará y pondrá en la Cola aquellos Nodes que aún no han sido visitados. Como N y Q han sido visitados anteriormente, solo visitará R y lo pondrá en cola.
Orden de visita: QMNPR.
La cola contiene: (NPR).
Ahora, N se quita de la cola.
La cola contiene: (PR).
Explora N, encuentra sus vecinos { M, O, Q }. Como M y Q han sido visitados anteriormente, solo visitará y pondrá en cola a O.
Orden de visita: QMNPRO.
La cola contiene: (PRO).
Ahora, P se elimina de la cola.
La cola contiene: (RO).
Explora P, encuentra a sus vecinos { O, Q }. Como O y Q se han visitado anteriormente, NO se pondrá en cola.
Ahora, R se quita de la cola.
La cola contiene: (O).
Explora R, encuentra a su vecino { M }. Como M ha sido visitado anteriormente, NO se pondrá en cola.
Ahora, O se quita de la cola.
La cola contiene : ( ) .
Explora O, encuentra a sus vecinos { N, P }. Como ambos han sido visitados anteriormente, NO se pondrá en cola.
Ahora Queue está vacío, por lo que BFS se detiene aquí.
Y el orden de visita ha sido: QMNPRO.
El pseudocódigo para la explicación anterior se puede encontrar en https://en.wikipedia.org/wiki/Breadth-first_search
Cuestionario de esta pregunta
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA