Algoritmos em Python

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.

  • Intermediário
  • 2 min de leitura
  • 1 exemplo executável

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.

Da caverna ao código
visited.add(node)🧵 Marque este túnel como explorado
for neighbor in graph[node]:🔀 Olhe cada túnel a partir daqui
depth_first(neighbor, visited)⬇️ Entre mais fundo no primeiro não explorado
return order↩️ Beco sem saída: siga o barbante de volta
Vá fundo primeiro, depois volte e tente o próximo ramo.
Em uma frase

A 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

  1. visited.add(node) marca o nó, então os ciclos não causam recursão infinita.
  2. for neighbor in graph[node]: olha cada vizinho por vez.
  3. order.extend(depth_first(neighbor, visited)) explora todo o ramo abaixo de um vizinho antes do próximo.
  4. 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

Executar código →
main.py
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"))
Gerar um botão Run para este exemplo

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.

  1. Teste com uma lista vazia, uma lista de um único elemento e uma lista com valores repetidos.
  2. Imprima o estado depois de cada passo para ver o algoritmo trabalhando.
  3. Meça o tempo com 100, 1.000 e 10.000 elementos e compare com outra solução.
Executar no compilador Python →

Erros comuns

Usar um argumento padrão mutável

visited=set() seria compartilhado entre chamadas separadas.

Problema
def depth_first(node, visited=set()):
Correção
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.

Todos os desafios