Hola Mateo.
Hay un par de cosas que no me quedan claras.
Mencionás un algoritmo iterativo. Pero no está del todo claro cómo es, porque en principio podría haber muchos algoritmos iterativos. ¿Es similar al de la página 93 del libro, manteniendo, como se explica más abajo, el padre de cada vértice?
También hacés referencia a la propiedad 3.7, que es de un algoritmo recursivo. ¿Cómo se relaciona con el iterativo? ¿Cuáles son los x e y?
Aún con estas dudas de cómo es el algoritmo, me parece que, si solo te interesa determinar si existe un ciclo (no mostrar uno de ellos), lo podés saber si padre[v] ya está definido y, como bien decís, no es padre[u].
En cambio, si querés mostrar el ciclo, v debe ser un vértice que, además de no ser padre[u], ya está explorado. Y el ciclo sería v, u, padre[u], padre[padre[u]], ..., v.
Hay un par de cosas que no me quedan claras.
Mencionás un algoritmo iterativo. Pero no está del todo claro cómo es, porque en principio podría haber muchos algoritmos iterativos. ¿Es similar al de la página 93 del libro, manteniendo, como se explica más abajo, el padre de cada vértice?
También hacés referencia a la propiedad 3.7, que es de un algoritmo recursivo. ¿Cómo se relaciona con el iterativo? ¿Cuáles son los x e y?
Aún con estas dudas de cómo es el algoritmo, me parece que, si solo te interesa determinar si existe un ciclo (no mostrar uno de ellos), lo podés saber si padre[v] ya está definido y, como bien decís, no es padre[u].
En cambio, si querés mostrar el ciclo, v debe ser un vértice que, además de no ser padre[u], ya está explorado. Y el ciclo sería v, u, padre[u], padre[padre[u]], ..., v.