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.
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ᵀ: .
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)
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
def asignar(GT, v, g, comp):
if comp[v] is None:
comp[v] = g
for u in GT[v]:
asignar(GT, u, u, comp)
Antes de comprobarla: ¿cuántos grupos devuelve la versión sin reverse?
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é?