Busca em Profundidade (DFS - Depth-First Search)

1. O Labirinto do Minotauro

A DFS funciona como alguém explorando um labirinto com um novelo de lã (como Teseu). 1. Siga um caminho até onde der. 2. Se chegar num beco sem saída, volte (Backtracking) até a última bifurcação. 3. Tente outro caminho.

Diferente da BFS (que usa Fila/Níveis), a DFS usa uma Pilha (Stack) (geralmente a pilha de recursão do próprio sistema).

2. Algoritmo Recursivo

A implementação recursiva é elegante e curta.

Código Java

// Variáveis Globais (na classe da Solução)
boolean[] visited;
List<List<Integer>> adj;

public void dfs(int u) {
    // 1. Marca como visitado
    visited[u] = true;
    System.out.print(u + " "); // Pré-ordem
    
    // 2. Explora vizinhos
    for (int v : adj.get(u)) {
        if (!visited[v]) {
            dfs(v); // Chamada Recursiva
        }
    }
}

O Perigo do Stack Overflow

Se o grafo for uma “linha” de \(10^5\) nós (\(1 \to 2 \to 3 \dots \to 10^5\)), teremos \(10^5\) chamadas recursivas empilhadas. - O limite padrão da Stack do Java/C++ pode estourar (StackOverflowError). - Em competições, C++ geralmente aguenta, mas Java pode precisar de configuração (-Xss).

3. Classificação de Arestas e Ciclos

Para tirar o máximo proveito da DFS, classificamos os vértices em 3 cores (estados): 1. BRANCO (0): Não visitado. 2. CINZA (1): Em processamento (está na pilha de recursão). 3. PRETO (2): Finalizado (já exploramos todos os descendentes).

Detecção de Ciclos

  • Grafo Não-Direcionado: Se virmos uma aresta para um nó CINZA ou PRETO que não seja o nosso pai imediato, achamos um ciclo.
  • Grafo Direcionado: Só existe ciclo se encontrarmos uma aresta para um nó CINZA (Back Edge). Se for PRETO, é apenas um cruzamento (Cross Edge) ou avanço (Forward Edge), não ciclo.

Implementação de Detecção de Ciclo (Direcionado)

int[] state; // 0=White, 1=Gray, 2=Black

boolean hasCycle(int u) {
    state[u] = 1; // Pinta de Cinza (Entrando)
    
    for (int v : adj.get(u)) {
        if (state[v] == 1) {
            return true; // Achou nó cinza: CICLO! (Back Edge)
        }
        if (state[v] == 0) {
            if (hasCycle(v)) return true;
        }
    }
    
    state[u] = 2; // Pinta de Preto (Saindo)
    return false;
}

4. DFS Iterativa (Pilha Explícita)

Para evitar Stack Overflow ou ter controle manual, usamos uma Stack<Integer>.

public void dfsIterative(int start) {
    Stack<Integer> stack = new Stack<>();
    stack.push(start);
    visited[start] = true;
    
    while (!stack.isEmpty()) {
        int u = stack.pop();
        System.out.print(u + " ");
        
        for (int v : adj.get(u)) {
            if (!visited[v]) {
                visited[v] = true;
                stack.push(v);
            }
        }
    }
}

Nota: A ordem de visita pode diferir ligeiramente da versão recursiva dependendo da ordem que os vizinhos são empilhados.

5. Aplicações Típicas

A DFS é mais versátil que a BFS para propriedades estruturais: 1. Contar Componentes Conexos: Chame DFS em um loop para cada nó não visitado. 2. Ordenação Topológica: Use DFS e guarde os nós numa lista quando eles ficarem PRETOS (pós-ordem reversa). 3. Componentes Fortemente Conexos (SCC): Algoritmo de Kosaraju ou Tarjan (baseados em DFS). 4. Pontes e Articulações: Algoritmo de Tarjan para grafos não-direcionados. 5. Resolver Labirintos: Achar qualquer caminho da entrada à saída.

Complexidade

  • Tempo: \(O(V + E)\) (semelhante à BFS).
  • Espaço: \(O(V)\) no pior caso (grafo linha), tanto para recursão quanto pilha explícita.
Back to top