La búsqueda en profundidad con dos marcas más: un color por vértice, que cambia de blanco a gris al entrar y de gris a negro al salir, y un reloj que anota el instante de cada cambio. Con esas marcas, encontrar un ciclo es mirar el color del vértice al que llega la flecha.
Entrada: un grafo dirigido y un vértice de
arranque. Salida: para cada vértice alcanzable, el instante
d en que se pintó de gris y el instante f en que
se pintó de negro; y si alguna flecha llegó a un vértice gris.
hay: –| Vértice | Color | d | f |
|---|
Las filas grises son los vértices abiertos en este instante: los mismos que están en la pila.
u y mira la flecha u → v. ¿De qué color tiene que estar v para que esa flecha cierre un ciclo?d, f]. Tomando dos vértices cualesquiera, ¿cómo pueden quedar sus intervalos?Sin solución aquí. Esta función arranca en un
solo vértice y solo ve lo alcanzable desde él. Escriba
tiene_ciclo(G) que decida si todo el grafo tiene
algún ciclo, usando esta función y sin reiniciar los colores entre
arranques. Después, ordene los vértices del segundo grafo de mayor a
menor f y compare esa lista con la que devuelve el algoritmo
de Kahn.