Cada vez que el recorrido en profundidad mira una arista
(u, v), el color de v decide el tipo. Si
v está blanco, la arista lo descubre y es de árbol; si está
gris, v sigue en la pila de llamadas, es ancestro de
u y la arista es de retroceso; si está negro, la arista es de
avance cuando d[u] < d[v] y cruzada en el otro caso. En un
grafo no dirigido cada arista aparece en las dos listas, y la segunda vez
hay que reconocerla. El reloj suma uno al descubrir un vértice y uno al
terminarlo, y arranca en 1.
d/f encima
| Vértice | Estado | d | f |
|---|
La pregunta se abre cuando el recorrido del grafo termina.
En un grafo no dirigido el recorrido nunca deja una
arista cruzada ni una de avance. Demuéstrelo: suponga que al mirar
u–v el vértice v ya está negro y explique por qué
esa arista ya se había mirado desde v, con u gris.
Después tome el grafo dirigido de ocho vértices, cambie la lista del 0 por
[4, 2, 1] y prediga, antes de trazarlo, qué aristas cambian de
tipo y cuántas de retroceso quedan.