PUERTA | PUERTA-CS-2003 | Pregunta 21

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: DFS de un gráfico

1) Visits a node. 
2) Do following for every unvisited adjacent.
   a) Completely explores all vertices through current 
      adjacent using recursive call to DFS.

Puede haber cualquier DFS posible, ya que podemos elegir diferentes vértices como puntos de partida y podemos elegir adyacentes en diferentes órdenes.

(i) abeghf [Visita a, explora todos los adyacentes hasta b, y así sucesivamente..]. En este e adyacente de b se selecciona primero
(iii) abfhge [Visita a, explora todos los adyacentes hasta b, y así sucesivamente..]. En esta b, la f adyacente se elige primero
(iv) afghbe [Visita a, explora todas las adyacentes hasta f, y así sucesivamente..]. En esta f, la g adyacente se elige primero

(ii) abfehg no puede ser una respuesta ya que e se visita después de f [e no es un adyacente de f y todos los adjuntos de f aún no se han explorado]
Cuestionario de esta pregunta