Busca em profundidade (DFS) em Python
Nesta lição, você vai percorrer um grafo com a busca em profundidade, implementada com uma função recursiva.
Introdução
O problema
Para achar a saída de um labirinto, verificar se um grafo tem ciclo ou ordenar tarefas que dependem umas das outras, você precisa seguir um caminho até o fim antes de tentar outro. É isso que a busca em profundidade faz.
Pense assim
A busca em profundidade é como explorar uma caverna com um novelo de barbante. Você segue um túnel até onde ele vai. Em um beco sem saída, você segue o barbante de volta até a última bifurcação e tenta o próximo túnel. Você marca os túneis explorados para nunca andar neles duas vezes.
visited.add(node)🧵 Marque este túnel como exploradofor neighbor in graph[node]:🔀 Olhe cada túnel a partir daquidepth_first(neighbor, visited)⬇️ Entre mais fundo no primeiro não exploradoreturn order↩️ Beco sem saída: siga o barbante de voltaA busca em profundidade (DFS, depth-first search) explora um grafo seguindo um ramo o mais fundo possível antes de voltar (backtracking), normalmente com recursão ou uma pilha.
Pontos-chave
visited.add(node)marca o nó, então os ciclos não causam recursão infinita.for neighbor in graph[node]:olha cada vizinho por vez.order.extend(depth_first(neighbor, visited))explora todo o ramo abaixo de um vizinho antes do próximo.- O resultado visita D antes de C, porque o ramo de B termina primeiro.
Quando usar?
- Encontrar qualquer caminho, resolver labirintos e quebra-cabeças com backtracking.
- Detectar ciclos e ordenar tarefas com dependências (ordenação topológica).
- Explorar todas as partes conectadas de um grafo.
Quando não é preciso
- Você precisa do caminho mais curto: a busca em profundidade pode achar um caminho longo primeiro; use busca em largura.
- Grafos muito profundos: a recursão pode bater no limite do Python; use uma pilha explícita.
Visualizador de Busca em profundidade (DFS) em Python
O(V + E)Use Executar ou Passo para acompanhar cada comparação e movimento dos dados.
Código de exemplo
graph = {"A": ["B", "C"], "B": ["D"], "C": ["E"], "D": [], "E": []}
def depth_first(node, visited=None):
visited = visited or set()
visited.add(node)
order = [node]
for neighbor in graph[node]:
if neighbor not in visited:
order.extend(depth_first(neighbor, visited))
return order
print(depth_first("A"))
Resultado da execução
['A', 'B', 'D', 'C', 'E']
Explicação do código
O conjunto visited registra os vértices já visitados para evitar repetição e laços infinitos quando o grafo tem ciclos. Cada chamada recursiva entra em um vizinho ainda não visitado, então o programa visita A, B, D e só depois volta para visitar C e E. A pilha de chamadas faz o papel da pilha do algoritmo, e a complexidade é O(V + E).
Altere os valores e execute o programa no compilador Python online CodeUtility sem instalar Python.
Exercícios práticos
Tente modificar o código seguindo as sugestões abaixo. Mudar o código e observar o resultado ajuda você a entender muito mais do que só ler.
- Teste com uma lista vazia, uma lista de um único elemento e uma lista com valores repetidos.
- Imprima o estado depois de cada passo para ver o algoritmo trabalhando.
- Meça o tempo com 100, 1.000 e 10.000 elementos e compare com outra solução.
Erros comuns
Usar um argumento padrão mutável
visited=set() seria compartilhado entre chamadas separadas.
def depth_first(node, visited=set()):
def depth_first(node, visited=None):
visited = visited or set()
Terminou esta lição?
Marque como aprendida para acompanhar seu progresso.
Pratique com um desafio
Use o conteúdo desta lição para resolver um problema real. Cada desafio roda no navegador, com testes instantâneos e uma revisão por IA.
- Count Islands Count groups of connected land cells in a grid. Médio
- Strongly Connected Components Count groups of nodes that can all reach each other. Difícil
- Longest Path in a DAG Find the heaviest path in a task dependency graph. Difícil