← Volver a los ejercicios

Las dos pasadas de Kosaraju

Primero una búsqueda en profundidad sobre G que deja los vértices ordenados por tiempo de finalización decreciente; después el mismo recorrido sobre Gᵀ, recorriendo esa lista de izquierda a derecha. Cada llamada que encuentra su vértice sin asignar pinta un componente entero y no se sale de él. El dibujo cambia de G a Gᵀ cuando empieza la segunda pasada.

1. El grafo y la predicción

Entrada: un grafo dirigido en lista de adyacencia, con 8 vértices.  Salida: sus componentes fuertemente conexos, en orden topológico del grafo de componentes.

Grafo:

¿Cuántos componentes fuertemente conexos tiene?

2. Con qué vértice arranca la segunda pasada

¿Cuál queda de primero en ord?

3. Ejecute las dos pasadas

orden (se llena por f creciente): [ ]
Componentes: ninguno todavía
Paso 0 de 0
Compare el contador de la línea 16 con el de la línea 15: la mayoría de las llamadas a asignar se topan con un vértice que ya tiene componente y se devuelven sin hacer nada.

4. Una fila por componente

ComponenteNombre gVérticesTamaño

5. Por qué la segunda pasada va sobre Gᵀ

Si la segunda pasada se hiciera sobre G, con la misma lista ord, ¿qué se perdería?

6. Para llevarse

Sin solución aquí. En el primer grafo, ejecute la segunda pasada recorriendo ord al revés, de derecha a izquierda, y escriba los grupos que salen. Diga en qué paso de la demostración se rompe el argumento. Después agregue la flecha 7 → 0 y calcule a mano cuántos componentes quedan.