← Volver a los ejercicios

Encuentre la falla

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.

1. Construir el grafo

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

2. Crear las listas

def construir(n, aristas):
    G = [[]] * n
    for arista in aristas:
        G[arista[0]].append(arista[1])
        G[arista[1]].append(arista[0])
    return G

3. La búsqueda en amplitud

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

4. Recorrer todo el grafo

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

5. Para llevarse

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.