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.
Siete vértices y cinco flechas, con
el contador de entrada de cada uno. El orden correcto es
.
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
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)
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)
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?