Implemente um algoritmo de busca em largura para um grafo direcionado.

Passo 1

O que o enunciado pede e o que temos disponível.
  • Pedido: implementar um algoritmo de busca em largura (BFS) para um grafo direcionado.
  • Resultado esperado (decisão minha para a implementação): uma função que, dado um grafo direcionado e um vértice inicial, retorne:
    • as distâncias mínimas (em número de arestas) do vértice inicial até todos os vértices alcançáveis;
    • o predecessor (pai) de cada vértice na árvore gerada pela BFS (para reconstruir caminhos);
    • a ordem em que os vértices foram retirados da fila (ordem de visita nível a nível).
  • Formato do grafo escolhido: lista de adjacência representada por um dicionário Python que mapeia cada vértice para a lista de vizinhos (arestas saindo do vértice). Exemplo de grafo:
    • \texttt{\{1: [2,3], 2: [4], 3: [], 4: [1]\}}.
  • Observações importantes dadas pelo enunciado implícitas:
    • o grafo é direcionado, então aresta (u,v) não implica (v,u);
    • o algoritmo deve evitar visitar um mesmo vértice várias vezes (marcar visitado).
  • O que a implementação vai devolver exatamente: três objetos (em Python): \text{dist} (dicionário de distâncias; vértices inacessíveis terão valor \texttt{None}), \text{parent} (dicionário de predecessores; raiz tem \texttt{None}), e \text{order} (lista com a ordem de saída da fila).

Passo 2

Intuição do algoritmo (a “aula” rápida e amigável).
  • Busca em largura (BFS) explora o grafo em “camadas” a partir do vértice inicial: primeiro todos os vizinhos a distância 1, depois todos os vértices a distância 2, e assim por diante.
  • Mecanismo central: uma fila (FIFO). Quando um vértice é descoberto, ele é enfileirado; quando retirado da fila, seus vizinhos não descobertos são marcados, ganham distância e são enfileirados.
  • Propriedade importante: a primeira vez que um vértice é descoberto, a distância obtida é a menor possível (em número de arestas). Por isso podemos usar BFS para encontrar caminhos mínimos em grafos não ponderados.
  • Para evitar visitas repetidas, usamos uma marcação de “visitado” no momento em que enfileiramos (não apenas quando desenfileiramos). Isso evita enfileirar o mesmo vértice várias vezes.

Passo 3

Estruturas de dados necessárias e por que cada uma ajuda.
  • Grafo: dicionário Python \texttt{graph} onde \texttt{graph[u]} dá a lista de vizinhos \{v \mid (u,v)\text{ é aresta}\}é.
  • Fila: \texttt{collections.deque} — operações \texttt{append} e \texttt{popleft} são O(1).
  • Distâncias: dicionário \texttt{dist} com chave = vértice e valor = distância inteira \ge 0 ou \texttt{None} se não alcançável.
  • Predecessores: dicionário \texttt{parent} com chave = vértice e valor = vértice pai na árvore BFS (ou \texttt{None} para a raiz ou vértices não alcançados).
  • Ordem de visita: lista \texttt{order} que registra a sequência em que os vértices são retirados da fila (útil para depuração e para entender os níveis).
  • Por que inicializar distâncias com \texttt{None}? Porque isso diferencia vértices não visitados de visitados; quando visitamos, colocamos um número \ge 0.

Passo 4

Pseudocódigo passo a passo (para você entender o que o código faz).
  1. Reunir o conjunto de todos os vértices do grafo (incluindo vértices que aparecem apenas como destino). Isso evita esquecer vértices soltos.
  2. Inicializar \texttt{dist[v] = None} para todo vértice v.
  3. Inicializar \texttt{parent[v] = None} para todo vértice v.
  4. Se o vértice inicial \texttt{s} não estiver no conjunto de vértices, adicioná-lo.
  5. Criar uma fila vazia \texttt{Q}.
  6. Definir \texttt{dist[s] = 0}, \texttt{parent[s] = None} e enfileirar \texttt{s}.
  7. Enquanto \texttt{Q} não estiver vazia:
    • retirar (desenfileirar) \texttt{u} da frente;
    • adicionar \texttt{u} à lista \texttt{order};
    • para cada vizinho \texttt{v} em \texttt{graph.get(u, [])}:
      • se \texttt{dist[v]} for \texttt{None} (não visitado):
        • definir \texttt{dist[v] = dist[u] + 1};
        • definir \texttt{parent[v] = u};
        • enfileirar \texttt{v}.
  8. Ao final, retornar \texttt{dist}, \texttt{parent}, \texttt{order}.

Passo 5

Implementação detalhada em Python (estilo claro e prático).
  • Comentários rápidos sobre escolhas:
    • A função aceita um dicionário \texttt{graph} e um vértice inicial \texttt{start}.
    • É robusta a vértices que aparecem apenas como destino.
    • Retorna três estruturas: distâncias, predecessores e ordem de visita.
  • Código (leia com calma; explico linha a linha logo depois):
from collections import deque
from typing import Dict, List, Tuple, Any, Optional

def bfs(graph: Dict[Any, List[Any]], start: Any) -> Tuple[Dict[Any, Optional[int]], Dict[Any, Optional[Any]], List[Any]]:
    """
    Busca em largura (BFS) em um grafo direcionado representado por lista de adjacência.

    Parâmetros:
    - graph: dicionário onde graph[u] é a lista de vizinhos v tais que existe aresta (u,v).
    - start: vértice inicial da busca.

    Retorna:
    - dist: dicionário com a menor distância (número de arestas) de 'start' a cada vértice.
            Vértices inalcançáveis têm valor None.
    - parent: dicionário com o predecessor de cada vértice na árvore BFS (None se sem predecessor).
    - order: lista com a ordem em que os vértices foram retirados da fila (ordem de visita por níveis).
    """
    # 1) Reunir todos os vértices (chaves + alvos nas listas de adjacência)
    nodes = set(graph.keys())
    for nbrs in graph.values():
        for v in nbrs:
            nodes.add(v)
    # Garantir que o start esteja nos nós (caso seja um vértice isolado não listado)
    nodes.add(start)

    # 2) Inicializar distâncias e predecessores
    dist: Dict[Any, Optional[int]] = {v: None for v in nodes}
    parent: Dict[Any, Optional[Any]] = {v: None for v in nodes}
    order: List[Any] = []

    # 3) Preparar a fila e iniciar pelo vértice start
    q = deque()
    dist[start] = 0
    parent[start] = None
    q.append(start)

    # 4) Laço principal da BFS
    while q:
        u = q.popleft()
        order.append(u)
        # Percorrer vizinhos de u (usar graph.get para lidar com vértices sem lista)
        for v in graph.get(u, []):
            if dist[v] is None:           # não visitado
                dist[v] = dist[u] + 1
                parent[v] = u
                q.append(v)

    return dist, parent, order

def reconstruct_path(parent: Dict[Any, Optional[Any]], start: Any, target: Any) -> Optional[List[Any]]:
    """
    Reconstrói o caminho mínimo (em número de arestas) de 'start' até 'target' usando o dicionário parent.
    Retorna a lista de vértices do caminho (start ... target) ou None se target não for alcançável.
    """
    if parent.get(target) is None and target != start:
        # Se parent[target] é None e target != start, então target não foi alcançado.
        return None
    path = []
    cur = target
    while cur is not None:
        path.append(cur)
        if cur == start:
            break
        cur = parent.get(cur)
    path.reverse()
    return path

Passo 6

Explicação linha a linha (detalhando pontos que costumam confundir na prova).
  • Linha que reúne os nós: é comum esquecer vértices que aparecem só como destino. O laço
    • para cada lista de vizinhos \texttt{nbrs} faz \texttt{for v in nbrs: nodes.add(v)}.
    • Assim o conjunto \texttt{nodes} contém todos os vértices mencionados.
  • Inicialização:
    • \texttt{dist[v] = None} significa “ainda não descoberto”.
    • Quando descobrimos (enfileiramos) um vértice v definimos \texttt{dist[v] = dist[u] + 1} (porque v está a uma aresta a mais que u).
    • Notar que marcamos \texttt{dist[v]} no momento de enfileirar; isso impede que enfileiremos v várias vezes.
  • Uso de \texttt{graph.get(u, [])}:
    • Garante que, se u não for chave em \texttt{graph} (vértice sem arestas de saída), iteramos uma lista vazia e não ocorre erro.
  • Reconstrução de caminho:
    • A função \texttt{reconstruct\_path} segue pais até a raiz; se não chegar ao start, o target não é alcançável.
  • Motivo de retornar \texttt{order}:
    • Útil pra ver os níveis; o prefixo até um certo índice contém todos os vértices visitados até aquele momento.

Passo 7

Complexidade e observações práticas.
  • Tempo: cada vértice é enfileirado no máximo uma vez; para cada vértice visitado percorremos todas as suas arestas de saída uma vez. Logo a complexidade é \mathcal{O}(|V| + |E|).
  • Espaço adicional (além do grafo): armazenamos \texttt{dist}, \texttt{parent} e \texttt{order}, então o espaço extra é \mathcal{O}(|V|).
  • Cuidados em prova/olímpiada:
    • Se os vértices forem números de 0 a n-1, usar listas em vez de dicionários é mais rápido e simples.
    • Sempre marque ao enfileirar (não ao desenfileirar) para evitar múltiplas ocorrências na fila.
    • Em grafos direcionados atenção a direção das arestas: (u,v) permite visitar v a partir de u, mas não o contrário.

Passo 8

Um exemplo pequeno para fixar (aplico a implementação acima e mostro saída esperada).
  • Considere \texttt{graph = \{1: [2,3], 2: [4], 3: [4], 4: []\}} e \texttt{start = 1}.
  • Resultado esperado:
    • \texttt{dist = \{1:0, 2:1, 3:1, 4:2\}}
    • \texttt{parent = \{1:None, 2:1, 3:1, 4:2\}} ou \texttt{4:3} dependendo da ordem dos vizinhos (ambas corretas se distâncias iguais).
    • \texttt{order} será algo como \texttt{[1,2,3,4]} (a ordem entre 2 e 3 depende da lista de adjacência).

Resposta

from collections import deque
from typing import Dict, List, Tuple, Any, Optional

def bfs(graph: Dict[Any, List[Any]], start: Any) -> Tuple[Dict[Any, Optional[int]], Dict[Any, Optional[Any]], List[Any]]:
    """
    Busca em largura (BFS) em um grafo direcionado representado por lista de adjacência.

    Parâmetros:
    - graph: dicionário onde graph[u] é a lista de vizinhos v tais que existe aresta (u,v).
    - start: vértice inicial da busca.

    Retorna:
    - dist: dicionário com a menor distância (número de arestas) de 'start' a cada vértice.
            Vértices inalcançáveis têm valor None.
    - parent: dicionário com o predecessor de cada vértice na árvore BFS (None se sem predecessor).
    - order: lista com a ordem em que os vértices foram retirados da fila (ordem de visita por níveis).
    """
    # 1) Reunir todos os vértices (chaves + alvos nas listas de adjacência)
    nodes = set(graph.keys())
    for nbrs in graph.values():
        for v in nbrs:
            nodes.add(v)
    # Garantir que o start esteja nos nós (caso seja um vértice isolado não listado)
    nodes.add(start)

    # 2) Inicializar distâncias e predecessores
    dist: Dict[Any, Optional[int]] = {v: None for v in nodes}
    parent: Dict[Any, Optional[Any]] = {v: None for v in nodes}
    order: List[Any] = []

    # 3) Preparar a fila e iniciar pelo vértice start
    q = deque()
    dist[start] = 0
    parent[start] = None
    q.append(start)

    # 4) Laço principal da BFS
    while q:
        u = q.popleft()
        order.append(u)
        # Percorrer vizinhos de u (usar graph.get para lidar com vértices sem lista)
        for v in graph.get(u, []):
            if dist[v] is None:           # não visitado
                dist[v] = dist[u] + 1
                parent[v] = u
                q.append(v)

    return dist, parent, order

def reconstruct_path(parent: Dict[Any, Optional[Any]], start: Any, target: Any) -> Optional[List[Any]]:
    """
    Reconstrói o caminho mínimo (em número de arestas) de 'start' até 'target' usando o dicionário parent.
    Retorna a lista de vértices do caminho (start ... target) ou None se target não for alcançável.
    """
    if parent.get(target) is None and target != start:
        return None
    path = []
    cur = target
    while cur is not None:
        path.append(cur)
        if cur == start:
            break
        cur = parent.get(cur)
    path.reverse()
    return path

Exercícios relacionados