Busca em profundidade (DFS)
Última atualização
A busca em profundidade explora um grafo indo o mais fundo possível por cada ramo antes de retroceder. Começando por um nó de origem, ela visita um vizinho, depois o vizinho desse vizinho, e assim por diante até chegar a um beco sem saída (um nó sem vizinhos não visitados), momento em que retrocede e tenta o próximo ramo. Pressione reproduzir acima para vê-la descer por um caminho, atingir o fundo e sair.
A DFS é expressa naturalmente com uma pilha: seja uma pilha explícita (como animada aqui) ou a pilha de chamadas via recursão. Ela visita cada nó e aresta uma vez, portanto executa em tempo O(V + E) para um grafo com V vértices e E arestas.
Complexidade de tempo e espaço
| Medida | Complexidade | Notas |
|---|---|---|
| Tempo | O(V + E) | Cada vértice e aresta é visitado uma vez |
| Espaço | O(V) | Pilha + conjunto de visitados, no pior caso todos os nós |
| Travessia | Mais profundo primeiro | Segue um ramo até o fim antes dos outros |
| Estrutura de dados | Pilha (ou recursão) | A ordem LIFO impulsiona o comportamento em profundidade |
Passo a passo
| Passo | O que acontece |
|---|---|
| 1 | Empilhe o nó de origem na pilha. |
| 2 | Desempilhe um nó; se já foi visitado, ignore-o. |
| 3 | Marque-o como visitado e registre a aresta que o alcançou. |
| 4 | Empilhe todos os seus vizinhos não visitados. |
| 5 | Repita até que a pilha esteja vazia. |
Exemplo resolvido
DFS iterativa a partir de A no grafo A → [B, C], B → [D], C → [E], empilhando os vizinhos na ordem indicada (a pilha LIFO desempilha primeiro o último empilhado):
| Passo | Pilha (topo à direita) | Visitados | Ação |
|---|---|---|---|
| 1 | [A] | {} | Empilha a origem A. |
| 2 | [B, C] | {A} | Desempilha A, marca visitado, empilha os vizinhos B e depois C. |
| 3 | [B, E] | {A, C} | Desempilha C, marca visitado, empilha o vizinho E. |
| 4 | [B] | {A, C, E} | Desempilha E, marca visitado, sem vizinhos. |
| 5 | [D] | {A, C, E, B} | Desempilha B, marca visitado, empilha o vizinho D. |
| 6 | [] | {A, C, E, B, D} | Desempilha D, marca visitado, pilha vazia: concluído. |
Quando usar DFS
| Use quando | Evite quando |
|---|---|
| Você precisa de detecção de ciclos, ordenação topológica ou encontrar componentes conexas. | Você precisa do caminho mais curto em um grafo não ponderado: isso é feito pela BFS, não pela DFS. |
| O grafo é largo e raso, então uma pilha usa muito menos memória que uma fila com muitos nós de fronteira. | O grafo é muito profundo e você usa recursão: a pilha de chamadas pode estourar. |
| Você quer explorar caminhos de forma exaustiva, como na resolução de labirintos ou na busca com backtracking. | Você precisa descobrir os nós na ordem de distância a partir da origem. |
| Você verifica alcançabilidade ou se existe um caminho entre dois nós. | Você deve garantir o número mínimo de arestas no caminho encontrado. |
Código de Depth-First Search
Uma implementação limpa e executável de Depth-First Search em Python, JavaScript, Java, C++, C. Escolha uma linguagem, copie o código ou abra-o já carregado no Playground da Coddy.
Código de Depth-First Search em Python
Python
1def dfs(graph, node, visited):2 visited.add(node)3 order = [node]4 for neighbor in graph[node]:5 if neighbor not in visited:6 order.extend(dfs(graph, neighbor, visited))7 return order8
9
10graph = {11 "A": ["B", "C"],12 "B": ["D", "E"],13 "C": ["F"],14 "D": [],15 "E": ["F"],16 "F": [],17}18
19order = dfs(graph, "A", set())20print("DFS order:", " -> ".join(order))Código de Depth-First Search em JavaScript
JavaScript
1const graph = {2 A: ["B", "C"],3 B: ["D", "E"],4 C: ["F"],5 D: [],6 E: ["F"],7 F: [],8};9
10function dfs(node, visited = new Set(), order = []) {11 if (visited.has(node)) return order;12 visited.add(node);13 order.push(node);14 for (const next of graph[node]) {15 dfs(next, visited, order);16 }17 return order;18}19
20console.log("DFS from A:", dfs("A").join(" -> "));Código de Depth-First Search em Java
Java
1import java.util.List;2
3public class Main {4 static List<List<Integer>> adj = List.of(5 List.of(1, 2), // neighbors of 06 List.of(0, 3, 4), // neighbors of 17 List.of(0, 5), // neighbors of 28 List.of(1),9 List.of(1, 5),10 List.of(2, 4)11 );12 static boolean[] visited = new boolean[6];13
14 static void dfs(int node) {15 visited[node] = true;16 System.out.print(" " + node);17 for (int next : adj.get(node)) {18 if (!visited[next]) dfs(next);19 }20 }21
22 public static void main(String[] args) {23 System.out.print("DFS from 0:");24 dfs(0);25 System.out.println();26 }27}Código de Depth-First Search em C++
C++
1#include <iostream>2#include <vector>3
4void dfs(int node, const std::vector<std::vector<int>>& adj,5 std::vector<bool>& visited) {6 visited[node] = true;7 std::cout << node << " ";8 // Recurse into every unvisited neighbor9 for (int next : adj[node]) {10 if (!visited[next]) dfs(next, adj, visited);11 }12}13
14int main() {15 // 6-node undirected graph as an adjacency list16 std::vector<std::vector<int>> adj = {17 {1, 2}, // 018 {0, 3, 4}, // 119 {0, 5}, // 220 {1}, // 321 {1, 5}, // 422 {2, 4}, // 523 };24 std::vector<bool> visited(adj.size(), false);25 std::cout << "DFS from node 0: ";26 dfs(0, adj, visited);27 std::cout << "\n";28 return 0;29}Código de Depth-First Search em C
C
1#include <stdbool.h>2#include <stdio.h>3
4#define N 65
6// 6-node undirected graph as an adjacency matrix7int adj[N][N] = {8 {0, 1, 1, 0, 0, 0},9 {1, 0, 0, 1, 1, 0},10 {1, 0, 0, 0, 0, 1},11 {0, 1, 0, 0, 0, 0},12 {0, 1, 0, 0, 0, 1},13 {0, 0, 1, 0, 1, 0},14};15bool visited[N];16
17void dfs(int node) {18 visited[node] = true;19 printf("%d ", node);20 // Recurse into every unvisited neighbor21 for (int next = 0; next < N; next++) {22 if (adj[node][next] && !visited[next]) dfs(next);23 }24}25
26int main(void) {27 printf("DFS from node 0: ");28 dfs(0);29 printf("\n");30 return 0;31}Perguntas frequentes sobre a busca em profundidade
Qual é a complexidade de tempo da DFS?
A DFS executa em tempo
O(V + E), onde V é o número de vértices e E o de arestas, porque visita cada vértice uma vez e examina cada aresta uma vez. Usa espaço O(V) para a pilha e o conjunto de visitados.Qual é a diferença entre DFS e BFS?
A DFS usa uma pilha e mergulha fundo por um ramo antes de retroceder, enquanto a BFS usa uma fila e explora nível por nível, primeiro os nós mais próximos. A BFS encontra o caminho mais curto em um grafo não ponderado; a DFS não, mas usa menos memória em grafos largos e é natural para tarefas como detecção de ciclos e ordenação topológica.
A DFS é recursiva ou iterativa?
Ambas funcionam. A versão recursiva usa implicitamente a pilha de chamadas do programa e é muito concisa; a versão iterativa usa uma pilha explícita (como a animação aqui) e evita estouros de pilha por recursão profunda em grafos grandes.
Quando devo usar DFS em vez de BFS?
Use DFS quando precisar explorar caminhos inteiros: detecção de ciclos, ordenação topológica, componentes conexas ou busca com backtracking como resolver um labirinto. Ela também usa menos memória em grafos largos, já que a pilha só contém a fronteira de um ramo por vez. Recorra à BFS quando precisar do caminho mais curto em um grafo não ponderado ou dos nós em ordem de distância a partir da origem.
A DFS consegue encontrar o caminho mais curto?
Não de forma confiável. A DFS retorna o primeiro caminho que encontra, que muitas vezes não é o de menos arestas, porque ela se compromete a mergulhar fundo em vez de se expandir uniformemente. Para caminhos mais curtos em um grafo não ponderado use BFS, e para grafos ponderados use o algoritmo de Dijkstra.
Por que a DFS precisa de um conjunto de visitados?
Sem um conjunto de visitados, a DFS revisitará nós alcançáveis por vários caminhos e, em um grafo cíclico, entrará em loop infinito. Marcar um nó como visitado ao desempilhá-lo (e ignorar desempilhamentos já visitados) garante que cada nó seja processado uma vez e mantém o tempo de execução em
O(V + E). Um erro comum é marcar os nós como visitados apenas ao desempilhar enquanto ainda se empilham duplicatas, o que é correto mas pode deixar entradas obsoletas na pilha que precisam ser ignoradas.Recursos relacionados
Mais visualizações
