← Volver a los ejercicios

Los colores y los tiempos del DFS

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.

1. El grafo

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.

Grafo:

blanco: sin tocar gris: abierto negro: terminado en la pila
¿En cuánto queda el reloj al terminar?

2. Ejecute y mire los colores

Versión:
Reloj: 0
Llamadas: vacía
hay: –
Paso 0 de 0
La flecha que se está mirando queda azul; si llega a un vértice gris, roja.

3. Las marcas de cada vértice

VérticeColordf

Las filas grises son los vértices abiertos en este instante: los mismos que están en la pila.

4. Qué color delata un ciclo

La búsqueda está en u y mira la flecha u → v. ¿De qué color tiene que estar v para que esa flecha cierre un ciclo?

5. Cómo quedan los intervalos

A cada vértice le queda el intervalo [d, f]. Tomando dos vértices cualesquiera, ¿cómo pueden quedar sus intervalos?

6. Para llevarse

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.