DFS, Recursão e Pilhas Iterativas
Explore profundamente e evite limites de recursão.
DFS, Recursão e Pilhas Iterativas é uma aula grátis de Coding Interview Prep no CoddyKit. Esta é a aula 3 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Coding Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Coding Interview Prep inclui 4 aulas no total.
O que DFS faz
DFS avança o máximo possível por um caminho, depois recua e tenta o próximo. Pense em explorar um labirinto, corredor por corredor. 🧭
DFS versus BFS
BFS se espalha em camadas; DFS mergulha primeiro em profundidade. Ambos visitam todos os nós alcançáveis, mas em uma ordem muito diferente.
A estrutura recursiva
O DFS recursivo marca um nó como visitado e depois chama a si mesmo para cada vizinho não visitado. A pilha de chamadas se lembra de onde retornar.
def dfs(u):
visited[u] = True
for v in adj[u]:
if not visited[v]:
dfs(v)Marcar antes de chamar recursivamente
Defina visitado ao entrar em um nó, antes de explorar os vizinhos. Caso contrário, ciclos fazem DFS entrar em recursão infinita.
A armadilha do limite de recursão
O Python limita a recursão a cerca de 1000 chamadas. Um grafo profundo provoca um RecursionError, que aparece como um veredito de erro em tempo de execução.
Aumentar o limite
Uma solução rápida é elevar o limite com setrecursionlimit. Defina-o acima da profundidade máxima esperada antes de executar DFS.
import sys
sys.setrecursionlimit(300000)Usar a versão iterativa
A solução mais segura é um DFS iterativo usando sua própria pilha. Sem profundidade de chamadas, não há falha de recursão.
stack = [start]Remover do topo da pilha
A cada etapa, retire o elemento do topo da pilha. O princípio último a entrar, primeiro a sair mantém DFS avançando primeiro pelo caminho mais recente.
u = stack.pop()Inserir os vizinhos na pilha
Depois de remover u, insira cada vizinho não visitado na pilha. Marque-os para que não sejam inseridos novamente.
for v in adj[u]:
if not visited[v]:
visited[v] = True
stack.append(v)O laço iterativo completo
Repita a remoção e a inserção enquanto a pilha contiver nós. Quando ela esvaziar, todos os nós alcançáveis terão sido visitados.
while stack:
u = stack.pop()
for v in adj[u]:
if not visited[v]:
visited[v] = True
stack.append(v)O mesmo custo de BFS
Assim como BFS, DFS visita cada nó e aresta uma vez, portanto é executado em O(n + m). Escolha-o de acordo com a ordem adequada à tarefa.
Verificação rápida
Seu DFS recursivo falha em um grafo profundo. Por quê?
Recapitulação
Você executa DFS recursivamente ou com sua própria pilha, marca os nós como visitados ao entrar e muda para a versão iterativa quando o grafo é profundo. 🎉
Perguntas Frequentes
A aula “DFS, Recursão e Pilhas Iterativas” é grátis?
Sim — o texto completo de “DFS, Recursão e Pilhas Iterativas” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Coding Interview Prep, atualize para CoddyKit PRO. O curso de Coding Interview Prep inclui 4 aulas no total.
O que vou aprender em “DFS, Recursão e Pilhas Iterativas”?
Explore profundamente e evite limites de recursão. Você pratica Coding Interview Prep com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar Coding Interview Prep?
Nenhuma experiência prévia é necessária. Coding Interview Prep no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 3 de 4.
Quanto tempo leva a aula “DFS, Recursão e Pilhas Iterativas”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de Coding Interview Prep?
Sim. Cada aula de Coding Interview Prep inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- Listas de Adjacência a partir da Entrada
- BFS para Caminhos Mínimos sem Pesos
- DFS, Recursão e Pilhas Iterativas
- Componentes Conexos e Preenchimento por Inundação