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 opción (A) es MNOPQR. No puede ser un BFS ya que el recorrido comienza con M, pero O se visita antes que N y Q. En BFS, todos los adyacentes deben visitarse antes que los adyacentes de los adyacentes.
La opción (B) es NQMPOR. Tampoco puede ser BFS, porque aquí se visita P antes que O.
(C) y (D) coinciden con QMNP. Vemos que M se agregó a la cola antes que N y P (porque M viene antes que NP en QMNP). Debido a que R es el vecino de M, se agrega a la cola antes que el vecino de N y P (que es O). Así, R es visitado antes que O.
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