Algoritmos | Gráficos transversales | Pregunta 12 – Part 2

Considere el siguiente gráfico,

Entre las siguientes secuencias:

(I) a b e g h f 
(II) a b f e h g
(III) a b f h g e 
(IV) a f g h b e  

¿Cuáles son los primeros recorridos en profundidad del gráfico anterior?
(A) Solo I, II y IV
(B) Solo I y IV
(C) Solo II, III y IV
(D) Solo I, III y IV

Respuesta: (D)
Explicación: Podemos verificar todos los DFS para las siguientes propiedades.

In DFS, if a vertex 'v' is visited
after 'u', then one of the following is true.
1) (u, v) is an edge.
     u
   /   \
  v     w
 /     / \
x     y   z

2) 'u' is a leaf node.
     w
   /   \
  x     v
 /     / \
u     y   z

En DFS , después de visitar un Node, primero recurrimos para todos los niños no visitados. Si no hay hijos no visitados (u es una hoja), entonces el control vuelve al padre y luego el padre visita a los siguientes hijos no visitados.
Cuestionario de esta pregunta