Equipe Rust Brasil 9 min de leitura

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.

rust algoritmos grafos dfs busca-em-profundidade

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 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

use std::collections::HashMap;

// Lista de adjacência com Vec<Vec<usize>>
fn criar_grafo(num_vertices: usize, arestas: &[(usize, usize)]) -> Vec<Vec<usize>> {
    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

CasoTempoEspaço
MelhorO(1)O(V)
MédioO(V + E)O(V)
PiorO(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

use std::collections::HashSet;

/// DFS recursivo que retorna a ordem de visitação.
fn dfs_recursivo(
    grafo: &Vec<Vec<usize>>,
    vertice: usize,
    visitados: &mut HashSet<usize>,
    ordem: &mut Vec<usize>,
) {
    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)

use std::collections::HashSet;

/// DFS iterativo usando Vec como pilha.
fn dfs_iterativo(grafo: &Vec<Vec<usize>>, origem: usize) -> Vec<usize> {
    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

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<Vec<usize>>) -> 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<Vec<usize>>,
    vertice: usize,
    estados: &mut Vec<Estado>,
) -> 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

use std::collections::HashSet;

/// Encontra um caminho (não necessariamente o mais curto) entre origem e destino.
fn dfs_encontrar_caminho(
    grafo: &Vec<Vec<usize>>,
    atual: usize,
    destino: usize,
    visitados: &mut HashSet<usize>,
    caminho: &mut Vec<usize>,
) -> 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).
  • 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 para grafos sem peso ou Dijkstra para grafos com peso.

Comparação com Outros Algoritmos

CaracterísticaDFSBFSDijkstra
Estrutura de dadosPilha/RecursãoFila (VecDeque)Fila de prioridade
Caminho mínimo (sem peso)NaoSimSim (mas overkill)
Detecção de ciclosSim (natural)Sim (com adaptação)Nao
Ordenação topológicaSimSim (Kahn)Nao
Componentes fortemente conexosSim (Tarjan/Kosaraju)NaoNao
BacktrackingSim (ideal)NaoNao
Uso de memóriaO(V) — profundidadeO(V) — larguraO(V)
Complexidade de tempoO(V + E)O(V + E)O((V + E) log V)
Risco de stack overflowSim (versão recursiva)NaoNao

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