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:
-
.
-
- Observações importantes dadas pelo enunciado implícitas:
- o grafo é direcionado, então aresta
não implica ; - o algoritmo deve evitar visitar um mesmo vértice várias vezes (marcar visitado).
- o grafo é direcionado, então aresta
- O que a implementação vai devolver exatamente: três objetos (em Python):
(dicionário de distâncias; vértices inacessíveis terão valor ), (dicionário de predecessores; raiz tem ), e (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
, depois todos os vértices a distância , 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
onde dá a lista de vizinhos . - Fila:
— operações e são O(1). - Distâncias: dicionário
com chave = vértice e valor = distância inteira ou se não alcançável. - Predecessores: dicionário
com chave = vértice e valor = vértice pai na árvore BFS (ou para a raiz ou vértices não alcançados). - Ordem de visita: lista
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
? Porque isso diferencia vértices não visitados de visitados; quando visitamos, colocamos um número .
Passo 4
Pseudocódigo passo a passo (para você entender o que o código faz).
- Reunir o conjunto de todos os vértices do grafo (incluindo vértices que aparecem apenas como destino). Isso evita esquecer vértices soltos.
- Inicializar
para todo vértice . - Inicializar
para todo vértice . - Se o vértice inicial
não estiver no conjunto de vértices, adicioná-lo. - Criar uma fila vazia
. - Definir
, e enfileirar . - Enquanto
não estiver vazia: - retirar (desenfileirar)
da frente; - adicionar
à lista ; - para cada vizinho
em : - se
for (não visitado): - definir
; - definir
; - enfileirar
.
- definir
- se
- retirar (desenfileirar)
- Ao final, retornar
, , .
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
e um vértice inicial . - É robusta a vértices que aparecem apenas como destino.
- Retorna três estruturas: distâncias, predecessores e ordem de visita.
- A função aceita um dicionário
-
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
faz . - Assim o conjunto
contém todos os vértices mencionados.
- para cada lista de vizinhos
- Inicialização:
-
significa “ainda não descoberto”. - Quando descobrimos (enfileiramos) um vértice
definimos (porque está a uma aresta a mais que ). - Notar que marcamos
no momento de enfileirar; isso impede que enfileiremos várias vezes.
-
- Uso de
: - Garante que, se
não for chave em (vértice sem arestas de saída), iteramos uma lista vazia e não ocorre erro.
- Garante que, se
- Reconstrução de caminho:
- A função
segue pais até a raiz; se não chegar ao start, o target não é alcançável.
- A função
- Motivo de retornar
: - Ú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 é
- Espaço adicional (além do grafo): armazenamos
, e , então o espaço extra é . - Cuidados em prova/olímpiada:
- Se os vértices forem números de
a , 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:
permite visitar a partir de , mas não o contrário.
- Se os vértices forem números de
Passo 8
Um exemplo pequeno para fixar (aplico a implementação acima e mostro saída esperada).
- Considere
e . - Resultado esperado:
-
-
ou dependendo da ordem dos vizinhos (ambas corretas se distâncias iguais). -
será algo como (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