Consultas 2022

Hola,

El algoritmo de la izquierda es correcto, es el mismo algoritmo que se presenta en el libro. El algoritmo de la derecha difiere en en qué momento se marca como explorado un nodo. Como una vez explorado no se vuelve a apilar, ni se modifica su nodo padre, esto hace que cambie el orden en el que se recorren los nodos y cambie el árbol de recorrida que se obtiene. Por esto, el segundo algoritmo no es DFS.

Un ejemplo para ver esto puede ser un grafo que sea un ciclo de tres nodos $u$, $v$ y $w$. Si se aplican los algoritmos partiendo del nodo $v$, DFS recorre los nodos de modo que padre[$u$]=$w$ y padre[$w$]=$v$, mientras que en el segundo algoritmo se obtiene que padre[$u$]=$v$ y padre[$w$]=$v$. Observar que este segundo árbol no cumple con la propiedad (3.7) del libro (en este caso existe una arista entre $u$ y $w$, pero ninguno es ancestro del otro), que sabemos que sí se cumple para DFS.

Saludos,

Tatiana