Algoritmos y Estructuras de Datos - VJ1215

Ayuda del ejercicio 25.a del tema 6

La existencia de un ciclo en el grafo se puede detectar porque, durante la búsqueda en profundidad, un vértice v tiene entre sus arcos de salida un arco (v, w) y w no solamente ya ha sido visitado sino que además es un ascendiente de v en el bosque de llamadas recursivas: eso implica que la búsqueda ya ha recorrido un camino desde w hasta v, y el arco (v, w) cierra un ciclo.

Piensa cómo comprobar eficientemente que sucede eso.

Más ayuda

Para reconocer eficientemente que w es un ascendiente de v en el árbol de llamadas recursivas, cuando se está ejecutando la llamada que recibe v como argumento podemos comprobar que la llamada que recibe w ha empezado pero no ha terminado.

Piensa qué necesitas para eso.