Algoritmos y Estructuras de Datos (VJ1215)
Curso 2023/2024
Algoritmos y Estructuras de Datos (VJ1215)
Curso 2023/2024
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.
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.