PUERTA | GATE-CS-2017 (Conjunto 2) | Pregunta 22

Breath First Search (BFS) se implementó utilizando la estructura de datos de la cola.

¿Cuál de los siguientes es un orden posible para visitar los Nodes en el gráfico anterior?
(A) MNOPQR
(B) NQMPOR
(C) QMNROP
(D) POQNMR

Respuesta: (D)
Explicación: En BFS , imprimimos un Node inicial, luego su adyacente, luego el adyacente del adyacente, y así sucesivamente.

Option A : MNOPQR Wrong
We cannot visit "O" before "R" as we start from "M". 
Note that "O" is adjacent of adjacent for "M" and
"R" is adjacent of "M".

Option B : NQMPOR Wrong
We cannot visit "P" before "O" as we start from "N". 
Note that "P" is adjacent of adjacent for "N" and 
"O" is adjacent.

Option C : QMNROP Wrong
We cannot visit "R" before "O" as we start from "Q". 
Note that "R" is adjacent of adjacent for "Q" and
"O" is adjacent of "Q"

Option D : POQNMR Right
We visit "P", then its adjacent "O", "Q" and "N"
Finally we visit adjacent of adjacent "M" and "R"

Cuestionario de esta pregunta