Busca em Profundidade
Mergulha fundo em cada ramo antes de explorar o próximo — essencial para detecção de ciclos e travessia de árvores.
O(V+E)O(V+E)Como Funciona
Passo a passo do algoritmo
Comece pelo nó inicial (ou use uma pilha)
Visite o nó de partida e empilhe-o. A DFS usa uma pilha (LIFO) — explicitamente ou via recursão — para controlar quais nós ainda precisam ser explorados.
pilha = [início]; marcar início como visitadoMergulhe no primeiro vizinho não visitado
Pegue o nó do topo da pilha e explore seu primeiro vizinho ainda não visitado, indo o mais fundo possível antes de voltar.
atual = pilha.pop(); empilhar primeiro vizinho não visitadoRetroceda quando não há mais vizinhos
Se o nó atual não tem vizinhos não visitados, faça backtracking — desempilhe e volte ao nó anterior para tentar outros caminhos.
se sem vizinhos não visitados: pilha.pop() (backtrack)Continue até explorar todo o ramo
Repita o processo de aprofundar e retroceder até que toda a pilha esteja vazia. Cada ramo é totalmente explorado antes de partir para o próximo.
enquanto pilha não vazia: aprofundar ou retrocederResultado: travessia em profundidade
A DFS produz uma ordem de visita que mergulha completamente em cada ramo antes de explorar ramos irmãos — ideal para detectar ciclos e caminhos.
nós visitados em ordem de profundidadeImplementação
Código comentado em JavaScript e Python
// Versão recursiva (mais elegante)
function dfsRecursiva(grafo, atual, visitados = new Set(), ordem = []) {
visitados.add(atual);
ordem.push(atual);
for (const vizinho of grafo[atual]) {
if (!visitados.has(vizinho)) {
dfsRecursiva(grafo, vizinho, visitados, ordem);
}
}
return ordem;
}
// Versão iterativa (com pilha explícita)
function dfsIterativa(grafo, inicio) {
const visitados = new Set();
const pilha = [inicio];
const ordem = [];
while (pilha.length > 0) {
const atual = pilha.pop(); // LIFO — retira do topo
if (!visitados.has(atual)) {
visitados.add(atual);
ordem.push(atual);
// Empilha em ordem reversa para manter ordem original
for (const vizinho of [...grafo[atual]].reverse()) {
if (!visitados.has(vizinho)) {
pilha.push(vizinho);
}
}
}
}
return ordem;
}
// Exemplo de uso
const grafo = {
1: [2, 3], 2: [1, 4, 5], 3: [1, 6, 7],
4: [2], 5: [2, 6], 6: [3, 5, 7], 7: [3, 6]
};
console.log(dfsRecursiva(grafo, 1)); // [1, 2, 4, 5, 6, 3, 7]Playground
Visualize a busca em profundidade e o backtracking
Quando Usar
Cenários ideais para este algoritmo
Detecção de ciclos
A DFS detecta ciclos em grafos verificando se chegamos a um nó já na pilha de chamadas atual (ancestral).
Ordenação topológica
Para grafos acíclicos dirigidos (DAGs), a DFS produz uma ordenação topológica válida — essencial para resolução de dependências.
Resolução de labirintos
A DFS explora cada caminho até o fim antes de tentar outro — exatamente como um humano tentaria sair de um labirinto sistematicamente.
Componentes conectados
Identificar grupos de nós conectados entre si, encontrar componentes fortemente conectados (algoritmo de Tarjan é baseado em DFS).
Complexidade
Análise de desempenho por cenário
| Cenário | Tempo |
|---|---|
| Melhor caso | O(V+E) |
| Caso médio | O(V+E) |
| Pior caso | O(V+E) |