← Volver a los ejercicios

Tres fallas en Kahn

Tres versiones del algoritmo sobre el mismo grafo, cada una con una línea equivocada. Ninguna da error al correr: las tres devuelven una lista, y hay que mirarla para darse cuenta. Al señalar la falla aparece lo que devuelve cada versión.

El grafo

Siete vértices y cinco flechas, con el contador de entrada de cada uno. El orden correcto es .

1. El vecino que no entra

while len(cola) > 0:
    u = cola.popleft()
    orden.append(u)
    for v in G[u]:
        if entrada[v] == 0:
            cola.append(v)
        entrada[v] = entrada[v] - 1

2. La marca en vez del contador

visitado = [False] * n
cola = deque()
u = 0
while u < n:
    if entrada[u] == 0:
        cola.append(u)
        visitado[u] = True
    u = u + 1
orden = []
while len(cola) > 0:
    u = cola.popleft()
    orden.append(u)
    for v in G[u]:
        if not visitado[v]:
            visitado[v] = True
            cola.append(v)

3. La cola inicial

u = 0
while u < n:
    if entrada[u] == 0 and len(G[u]) > 0:
        cola.append(u)
    u = u + 1
orden = []
while len(cola) > 0:
    u = cola.popleft()
    orden.append(u)
    for v in G[u]:
        entrada[v] = entrada[v] - 1
        if entrada[v] == 0:
            cola.append(v)

4. Para llevarse

Sin solución aquí. Las tres versiones equivocadas devuelven una lista más corta o desordenada, y ninguna avisa. Escriba una función revisar(G, orden) que reciba un grafo y una lista y diga si es un orden topológico completo: úsela como prueba de las tres versiones de arriba. ¿Cuánto cuesta esa revisión comparada con el algoritmo?