PUERTA | Sudo GATE 2020 Mock III (24 de enero de 2019) | Pregunta 22

Considere el siguiente gráfico. Supongamos que queremos atravesarlo, comenzando en el Node A.

¿Cuál de las siguientes opciones es correcta con respecto a estas órdenes de desplazamiento?

I. A, G, F, B, C, H, D, E
II. A, G, H, F, C, D, E, B
III. A, C, B, F, G, D, H, E
IV. A, B, C, E, D, F, H, G 

(A) I y II son BFS, III y IV son DFS
(B) I y III son BFS, II y IV son DFS.
(C) I y IV son BFS, II y IV son DFS
(D) II y IV son BFS, I y III son DFS

Respuesta: (B)
Explicación: aquí hay dos ordenaciones posibles para BFS:

• A, G, F, B, C, H, D, E
• A, C, B, F, G, D, H, E 

Aquí hay dos ordenaciones posibles para DFS:

• A, G, H, F, C, D, E, B
• A, B, C, E, D, F, H, G 

Entonces, I y III son BFS, II y IV son DFS.

La opción (B) es correcta.
Cuestionario de esta pregunta