Consultas 2022

Hola Federico,

En BFS no se cumple necesariamente que si llegás a partir de un nodo $x$ a un nodo $u$ ya explorado, recorriendo por parent desde $u$ se llegue nuevamente al nodo $x$. Esto se cumple para DFS (3.7), pero no para BFS.

En el caso de BFS se sabe que ambos nodos tienen un ancestro en común, y se puede saber en qué capa están cada uno de los nodos (distancia al nodo inicial desde el cual llamé a BFS). Con esto se puede recorrer hacia atrás, usando el arreglo parent, a la vez los ancestros de ambos nodos $u$ y $x$, hasta llegar a el primer ancestro en común.

De todas formas, si se ejecutara DFS en vez de BFS igual no alcanza con ejecutarlo desde un solo nodo, ya que puede ocurrir que no se recorran todos los ciclos cuando se parte de un nodo solo (encuentra solo los ciclos en los que solamente una de las aristas del ciclo no pertenece al árbol DFS).

Saludos,
Tatiana