← Volver a los ejercicios

Tres fallas en Kosaraju

Tres versiones del algoritmo sobre el mismo grafo, cada una con una línea cambiada. Ninguna revienta al correr: las tres devuelven una lista de listas que parece una respuesta. Al señalar la línea aparece lo que devuelve esa versión y en qué se diferencia de la correcta.

El grafo

Siete vértices y nueve flechas: 0 → 1, 1 → 0, 0 → 2, 2 → 3, 3 → 2, 2 → 4, 3 → 5, 5 → 6, 6 → 5.
Respuesta correcta: .
ord = .
Listas de Gᵀ: .

1. La pasada que se sale del componente

def kosaraju(grafo):
    orden = orden_por_finalizacion(grafo)
    GT = grafo_transpuesto(grafo)
    comp = {}
    for v in grafo:
        comp[v] = None
    for v in orden:
        asignar(grafo, v, v, comp)
    return agrupar(grafo, comp, orden)

2. La lista que quedó al derecho

def orden_por_finalizacion(grafo):
    visitado = {}
    for v in grafo:
        visitado[v] = False
    orden = []
    for v in grafo:
        if not visitado[v]:
            orden_aux(grafo, v, visitado, orden)
    return orden

3. El componente que perdió su nombre

def asignar(GT, v, g, comp):
    if comp[v] is None:
        comp[v] = g
        for u in GT[v]:
            asignar(GT, u, u, comp)

4. Cuántos devuelve la segunda

Antes de comprobarla: ¿cuántos grupos devuelve la versión sin reverse?

5. Para llevarse

Sin solución aquí. Dibuje un grafo dirigido donde la primera versión, la que recorre G en vez de Gᵀ, devuelva por casualidad la respuesta correcta, y diga qué tiene ese grafo de particular. Después conteste: la tercera versión devuelve siempre un grupo por vértice, sin importar el grafo. ¿Por qué?