Cuatro programas que corren sin dar error y contestan mal. En cada uno hay exactamente una línea equivocada. Cuando la señale, aparece la salida de las dos versiones para ver qué tan lejos queda la respuesta.
El grafo es no dirigido, con 6 vértices y las aristas (0,2), (0,3), (1,2), (1,5), (2,3), (2,4), (4,5).
def construir(n, aristas):
G = []
u = 0
while u < n:
G.append([])
u = u + 1
for arista in aristas:
G[arista[0]].append(arista[1])
return G
def construir(n, aristas):
G = [[]] * n
for arista in aristas:
G[arista[0]].append(arista[1])
G[arista[1]].append(arista[0])
return G
def bfs(G, s):
visitado = [False] * len(G)
d = [-1] * len(G)
d[s] = 0
cola = deque()
cola.append(s)
while len(cola) > 0:
u = cola.popleft()
if not visitado[u]:
visitado[u] = True
for v in G[u]:
if not visitado[v]:
if d[v] == -1:
d[v] = d[u] + 1
cola.append(v)
return d
El problema pide visitar todos los vértices del grafo, no solo los alcanzables desde uno.
def recorrer_todo(G):
visitado = [False] * len(G)
orden = []
dfs(G, 0, visitado, orden)
return orden
Sin solución aquí. El error del caso 3 no cambia ni el orden de visita ni las distancias en el grafo de seis vértices: solo infla la cola. Construya un grafo donde esa diferencia sea grande —piense en cuántos vecinos comparte un vértice con sus compañeros de capa— y calcule, en términos de $V$ y $E$, cuántas entradas puede llegar a tener la cola con el error y sin él.