--- title: "Busca em Profundidade (DFS) em Rust" url: "https://rustlang.com.br/algoritmos/dfs/" markdown_url: "https://rustlang.com.br/algoritmos/dfs.MD" description: "Implementação completa da Busca em Profundidade (DFS) em Rust: versões recursiva e iterativa, detecção de ciclos, diagramas visuais e análise Big-O." date: "2026-02-24" author: "Equipe Rust Brasil" --- # Busca em Profundidade (DFS) em Rust Implementação completa da Busca em Profundidade (DFS) em Rust: versões recursiva e iterativa, detecção de ciclos, diagramas visuais e análise Big-O. A **Busca em Profundidade** (Depth-First Search, ou DFS) é um algoritmo de exploração de grafos que avança o mais fundo possível em cada ramo antes de retroceder (backtracking). Diferente do [BFS](/algoritmos/bfs/) que explora nível por nível, o DFS mergulha completamente em um caminho até não poder mais avançar, depois volta e tenta outro caminho. O DFS é a base de diversos algoritmos clássicos de grafos: detecção de ciclos, ordenação topológica, busca de componentes fortemente conexos (Tarjan, Kosaraju), resolução de labirintos e problemas de backtracking. Em Rust, pode ser implementado de forma recursiva (usando a pilha de chamadas) ou iterativa (usando uma pilha explícita com `Vec`). ## Como Funciona O DFS utiliza uma **pilha** (LIFO — Last In, First Out) para controlar a exploração. O algoritmo: 1. Empilha o vértice de origem e o marca como visitado. 2. Desempilha o vértice do topo. 3. Para cada vizinho não visitado, marca como visitado e empilha. 4. Repete os passos 2-3 até que a pilha esteja vazia. Na versão recursiva, a pilha de chamadas do sistema substitui a pilha explícita. ### Diagrama Visual — Backtracking Considere o seguinte grafo: ``` 0 / \ 1 2 / \ \ 3 4 5 | 6 ``` Lista de adjacência (vizinhos em ordem crescente): ``` 0 -> [1, 2] 1 -> [0, 3, 4] 2 -> [0, 5] 3 -> [1] 4 -> [1, 6] 5 -> [2] 6 -> [4] ``` Execução do DFS recursivo a partir do vértice 0: ``` Chamada | Vértice | Pilha de chamadas | Visitados | Ação ---------|---------|-------------------|----------------------|--------------------------- 1 | 0 | [0] | {0} | Visita 0, explora vizinho 1 2 | 1 | [0, 1] | {0, 1} | Visita 1, explora vizinho 3 3 | 3 | [0, 1, 3] | {0, 1, 3} | Visita 3, vizinho 1 já visitado | | [0, 1] | | BACKTRACK para 1 4 | 4 | [0, 1, 4] | {0, 1, 3, 4} | Visita 4, explora vizinho 6 5 | 6 | [0, 1, 4, 6] | {0, 1, 3, 4, 6} | Visita 6, vizinho 4 já visitado | | [0, 1, 4] | | BACKTRACK para 4 | | [0, 1] | | BACKTRACK para 1 | | [0] | | BACKTRACK para 0 6 | 2 | [0, 2] | {0, 1, 3, 4, 6, 2} | Visita 2, explora vizinho 5 7 | 5 | [0, 2, 5] | {0, 1, 3, 4, 6, 2, 5}| Visita 5, vizinho 2 já visitado | | [] | | BACKTRACK total -> FIM ``` Caminho de exploração visual: ``` 0 -> 1 -> 3 (volta) -> 4 -> 6 (volta, volta, volta) -> 2 -> 5 (volta, volta) FIM ``` Ordem de visitação: **0, 1, 3, 4, 6, 2, 5** ## Representação do Grafo ```rust use std::collections::HashMap; // Lista de adjacência com Vec> fn criar_grafo(num_vertices: usize, arestas: &[(usize, usize)]) -> Vec> { let mut grafo = vec![vec![]; num_vertices]; for &(u, v) in arestas { grafo[u].push(v); grafo[v].push(u); // Remover para grafo direcionado } grafo } // Lista de adjacência com HashMap (para vértices não numéricos) fn criar_grafo_generico() -> HashMap<&'static str, Vec<&'static str>> { let mut grafo = HashMap::new(); grafo.insert("A", vec!["B", "C"]); grafo.insert("B", vec!["A", "D"]); grafo.insert("C", vec!["A", "E"]); grafo.insert("D", vec!["B"]); grafo.insert("E", vec!["C"]); grafo } ``` ## Complexidade | Caso | Tempo | Espaço | |---------|----------|----------| | Melhor | O(1) | O(V) | | Médio | O(V + E) | O(V) | | Pior | O(V + E) | O(V) | Onde **V** = número de vértices e **E** = número de arestas. - **Tempo O(V + E):** cada vértice é visitado uma vez (O(V)) e cada aresta é examinada uma vez (O(E)). - **Espaço O(V):** a pilha de recursão (ou pilha explícita) pode crescer até V no pior caso (grafo em formato de lista/caminho linear). O conjunto de visitados também ocupa O(V). - **Atenção:** para grafos muito profundos, a versão recursiva pode causar **stack overflow**. Nesses casos, use a versão iterativa. ## Implementação em Rust ### DFS Recursivo ```rust use std::collections::HashSet; /// DFS recursivo que retorna a ordem de visitação. fn dfs_recursivo( grafo: &Vec>, vertice: usize, visitados: &mut HashSet, ordem: &mut Vec, ) { visitados.insert(vertice); ordem.push(vertice); for &vizinho in &grafo[vertice] { if !visitados.contains(&vizinho) { dfs_recursivo(grafo, vizinho, visitados, ordem); } } } fn main() { let mut grafo = vec![vec![]; 7]; let arestas = [(0,1), (0,2), (1,3), (1,4), (2,5), (4,6)]; for (u, v) in arestas { grafo[u].push(v); grafo[v].push(u); } let mut visitados = HashSet::new(); let mut ordem = Vec::new(); dfs_recursivo(&grafo, 0, &mut visitados, &mut ordem); println!("Ordem DFS recursivo: {:?}", ordem); // Saída: Ordem DFS recursivo: [0, 1, 3, 4, 6, 2, 5] } ``` ### DFS Iterativo (com Pilha Explícita) ```rust use std::collections::HashSet; /// DFS iterativo usando Vec como pilha. fn dfs_iterativo(grafo: &Vec>, origem: usize) -> Vec { let mut visitados = HashSet::new(); let mut pilha = Vec::new(); let mut ordem = Vec::new(); pilha.push(origem); while let Some(vertice) = pilha.pop() { if visitados.contains(&vertice) { continue; } visitados.insert(vertice); ordem.push(vertice); // Empilha vizinhos em ordem reversa para manter // a ordem natural de visitação (menor primeiro) for &vizinho in grafo[vertice].iter().rev() { if !visitados.contains(&vizinho) { pilha.push(vizinho); } } } ordem } fn main() { let mut grafo = vec![vec![]; 7]; let arestas = [(0,1), (0,2), (1,3), (1,4), (2,5), (4,6)]; for (u, v) in arestas { grafo[u].push(v); grafo[v].push(u); } let ordem = dfs_iterativo(&grafo, 0); println!("Ordem DFS iterativo: {:?}", ordem); // Saída: Ordem DFS iterativo: [0, 1, 3, 4, 6, 2, 5] } ``` ### Detecção de Ciclos em Grafo Direcionado ```rust use std::collections::HashSet; /// Estados de visitação para detecção de ciclos. #[derive(Clone, PartialEq)] enum Estado { NaoVisitado, EmProcessamento, // Na pilha de recursão atual Concluido, // Todos os descendentes já explorados } /// Detecta se há ciclo em um grafo direcionado usando DFS. fn tem_ciclo_direcionado(grafo: &Vec>) -> bool { let n = grafo.len(); let mut estados = vec![Estado::NaoVisitado; n]; for v in 0..n { if estados[v] == Estado::NaoVisitado { if dfs_detecta_ciclo(grafo, v, &mut estados) { return true; } } } false } fn dfs_detecta_ciclo( grafo: &Vec>, vertice: usize, estados: &mut Vec, ) -> bool { estados[vertice] = Estado::EmProcessamento; for &vizinho in &grafo[vertice] { match estados[vizinho] { Estado::EmProcessamento => return true, // Ciclo encontrado! Estado::NaoVisitado => { if dfs_detecta_ciclo(grafo, vizinho, estados) { return true; } } Estado::Concluido => {} // Já explorado, sem ciclo por aqui } } estados[vertice] = Estado::Concluido; false } fn main() { // Grafo direcionado SEM ciclo let grafo_aciclico = vec![ vec![1, 2], // 0 -> 1, 2 vec![3], // 1 -> 3 vec![3], // 2 -> 3 vec![], // 3 -> (nada) ]; println!("Grafo acíclico tem ciclo? {}", tem_ciclo_direcionado(&grafo_aciclico)); // Saída: Grafo acíclico tem ciclo? false // Grafo direcionado COM ciclo: 0->1->2->0 let grafo_ciclico = vec![ vec![1], // 0 -> 1 vec![2], // 1 -> 2 vec![0, 3], // 2 -> 0, 3 (ciclo 0->1->2->0) vec![], // 3 -> (nada) ]; println!("Grafo cíclico tem ciclo? {}", tem_ciclo_direcionado(&grafo_ciclico)); // Saída: Grafo cíclico tem ciclo? true } ``` ### DFS para Encontrar Caminho ```rust use std::collections::HashSet; /// Encontra um caminho (não necessariamente o mais curto) entre origem e destino. fn dfs_encontrar_caminho( grafo: &Vec>, atual: usize, destino: usize, visitados: &mut HashSet, caminho: &mut Vec, ) -> bool { visitados.insert(atual); caminho.push(atual); if atual == destino { return true; } for &vizinho in &grafo[atual] { if !visitados.contains(&vizinho) { if dfs_encontrar_caminho(grafo, vizinho, destino, visitados, caminho) { return true; } } } // Backtrack: remove o vértice atual do caminho caminho.pop(); false } fn main() { let mut grafo = vec![vec![]; 7]; let arestas = [(0,1), (0,2), (1,3), (1,4), (2,5), (4,6)]; for (u, v) in arestas { grafo[u].push(v); grafo[v].push(u); } let mut visitados = HashSet::new(); let mut caminho = Vec::new(); if dfs_encontrar_caminho(&grafo, 0, 6, &mut visitados, &mut caminho) { println!("Caminho encontrado: {:?}", caminho); } else { println!("Não há caminho."); } // Saída: Caminho encontrado: [0, 1, 4, 6] } ``` ## Exemplo de Execução Executando a detecção de ciclos no seguinte grafo direcionado: ``` 0 -----> 1 | | v v 2 -----> 3 ^ | | v 5 <----- 4 ``` ``` Arestas: 0->1, 0->2, 1->3, 2->3, 3->4, 4->5, 5->2 DFS a partir do vértice 0: Passo 1: Visita 0 (EmProcessamento) Passo 2: Visita 1 (EmProcessamento) Passo 3: Visita 3 (EmProcessamento) Passo 4: Visita 4 (EmProcessamento) Passo 5: Visita 5 (EmProcessamento) Passo 6: Vizinho 2 -> NaoVisitado Passo 7: Visita 2 (EmProcessamento) Passo 8: Vizinho 3 -> EmProcessamento! >>> CICLO DETECTADO: 3 -> 4 -> 5 -> 2 -> 3 Resultado: O grafo contém um ciclo. ``` ## Variações e Otimizações ### 1. DFS com Tempos de Descoberta e Finalização Registrar o tempo de descoberta e finalização de cada vértice é útil para classificar arestas (árvore, retorno, avanço, cruzamento) e para o algoritmo de componentes fortemente conexos de Tarjan. ### 2. DFS Limitado (Iterative Deepening) Combina DFS com limite de profundidade, incrementando o limite a cada iteração. Obtém a completude do BFS com o uso de memória do DFS. Útil quando o grafo é muito grande e a profundidade da solução é desconhecida. ### 3. DFS em Grafos Implícitos Para problemas de backtracking (N-rainhas, Sudoku, geração de permutações), o grafo nunca é construído explicitamente. Cada estado é um "vértice" e as transições são as "arestas", exploradas on-the-fly pelo DFS. ## Quando Usar Use DFS quando: - Precisa **detectar ciclos** em grafos direcionados ou não direcionados. - Quer realizar **ordenação topológica** (base para [Topological Sort](/algoritmos/topological-sort/)). - Precisa encontrar **componentes fortemente conexos** (algoritmos de Tarjan ou Kosaraju). - Está resolvendo problemas de **backtracking** (permutações, combinações, Sudoku, N-rainhas). - Quer verificar se existe **algum caminho** entre dois vértices (sem necessidade de ser o mais curto). - Precisa encontrar **pontes** e **pontos de articulação** em um grafo. **Evite DFS** quando precisa do **caminho mais curto** — use [BFS](/algoritmos/bfs/) para grafos sem peso ou [Dijkstra](/algoritmos/dijkstra/) para grafos com peso. ## Comparação com Outros Algoritmos | Característica | DFS | BFS | Dijkstra | |----------------------------|--------------------------|--------------------------|--------------------------| | Estrutura de dados | Pilha/Recursão | Fila (VecDeque) | Fila de prioridade | | Caminho mínimo (sem peso) | Nao | Sim | Sim (mas overkill) | | Detecção de ciclos | Sim (natural) | Sim (com adaptação) | Nao | | Ordenação topológica | Sim | Sim (Kahn) | Nao | | Componentes fortemente conexos | Sim (Tarjan/Kosaraju)| Nao | Nao | | Backtracking | Sim (ideal) | Nao | Nao | | Uso de memória | O(V) — profundidade | O(V) — largura | O(V) | | Complexidade de tempo | O(V + E) | O(V + E) | O((V + E) log V) | | Risco de stack overflow | Sim (versão recursiva) | Nao | Nao | ## Exercícios Práticos 1. **Todos os caminhos:** Dado um grafo direcionado acíclico (DAG), encontre **todos** os caminhos do vértice 0 ao vértice N-1 usando DFS com backtracking. 2. **Resolver labirinto:** Dada uma matriz 2D onde `0` é caminho livre e `1` é parede, use DFS para encontrar um caminho da entrada (0,0) à saída (n-1, m-1). Imprima o caminho encontrado. 3. **Componentes conexos:** Use DFS para contar o número de componentes conexos em um grafo não direcionado. Compare a implementação com a versão BFS. 4. **Classificação de arestas:** Implemente DFS com tempos de descoberta e finalização. Classifique cada aresta como aresta de árvore, retorno, avanço ou cruzamento. ## Veja Também - [`Vec` — Vetor dinâmico](/stdlib/vec/) — usado como pilha na versão iterativa do DFS - [`HashSet` — Conjunto hash](/stdlib/hashset/) — para rastrear vértices visitados - [`HashMap` — Mapa hash](/stdlib/hashmap/) — para representação de grafos com lista de adjacência - [`Option` — Tipo opcional](/stdlib/option/) — para tratar resultados opcionais na busca - [Busca em Largura (BFS)](/algoritmos/bfs/) — algoritmo complementar ao DFS - [Ordenação Topológica](/algoritmos/topological-sort/) — aplicação direta do DFS - [Algoritmo de Dijkstra](/algoritmos/dijkstra/) — caminho mínimo em grafos com peso