Lançado · em melhoria
Algorithm
A busca em grafos visita todos os vértices alcançáveis com BFS ou DFS e é a base de caminhos mínimos sem peso, componentes, ciclos e ordenação topológica.
Busca em grafos é o processo de visitar, exatamente uma vez, todos os vértices alcançáveis a partir de um vértice inicial seguindo as arestas. As duas estratégias fundamentais são a busca em largura (BFS), que usa uma fila para avançar camada por camada, e a busca em profundidade (DFS), que usa uma pilha ou recursão para seguir um caminho até o fim antes de voltar. Grafos costumam ser armazenados como listas de adjacência ou matrizes de adjacência, e grades 2D, como labirintos, também viram grafos quando cada célula é tratada como um vértice.
Malhas viárias, redes sociais, dependências entre tarefas e links da web são grafos. A BFS encontra caminhos mínimos quando todas as arestas têm o mesmo custo, enquanto a DFS é a base de componentes conexos, detecção de ciclos e ordenação topológica. Ferramentas de build que ordenam tarefas, coletores de lixo que decidem o que ainda é alcançável e a ferramenta de balde de tinta de um editor de imagens dependem de busca em grafos, e esse é um dos temas mais comuns em entrevistas técnicas.
Comece desenhando um grafo pequeno e acompanhando à mão como mudam a fila da BFS e a pilha de chamadas da DFS. Depois, implemente as duas por conta própria, prestando atenção ao momento em que os vértices são marcados como visitados e a como distâncias e pais são registrados. Em seguida, avance para caminhos mínimos em grades, contagem de componentes conexos e ordenação topológica com o algoritmo de Kahn.
Listas de adjacência usam memória O(V + E) e servem para grafos esparsos; matrizes verificam arestas em O(1), mas ocupam O(V^2).
Uma fila visita primeiro os vértices mais próximos, então, em grafos sem peso, a primeira distância atribuída é a menor.
Recursão ou pilha avançam em profundidade e voltam; é a base de componentes, detecção de ciclos e backtracking.
Em um grafo direcionado acíclico, o algoritmo de Kahn ou a ordem de término invertida da DFS gera uma ordem que respeita as dependências.
O programa monta um grafo não direcionado de seis vértices como lista de adjacência em um dicionário e imprime, com uma BFS baseada em deque, o menor número de arestas de A até cada vértice e, com uma DFS recursiva, a ordem de visita. As duas funções registram os vértices visitados para não processar nenhum duas vezes.
graph_traversal.py
from collections import deque
graph = {
"A": ["B", "C"],
"B": ["A", "D"],
"C": ["A", "D", "E"],
"D": ["B", "C", "F"],
"E": ["C", "F"],
"F": ["D", "E"],
}
def bfs(start):
"""Shortest number of edges from start to every reachable vertex."""
dist = {start: 0}
queue = deque([start])
while queue:
node = queue.popleft()
for nxt in graph[node]:
if nxt not in dist:
dist[nxt] = dist[node] + 1
queue.append(nxt)
return dist
def dfs(start):
"""Vertices in depth-first visiting order."""
order, seen = [], set()
def visit(node):
seen.add(node)
order.append(node)
for nxt in graph[node]:
if nxt not in seen:
visit(nxt)
visit(start)
return order
print(bfs("A")) # {'A': 0, 'B': 1, 'C': 1, 'D': 2, 'E': 2, 'F': 3}
print(dfs("A")) # ['A', 'B', 'D', 'C', 'E', 'F']
python graph_traversal.pySeis capítulos que levam você da instalação aos conceitos essenciais de Busca em grafos.
Tire dúvidas, compartilhe experiências e troque opiniões sobre Busca em grafos.
Ainda não há discussões. Comece a primeira.
0 comentários
Fazer login · Faça login para deixar um comentário.
Seja o primeiro a comentar.