DFS (Busca em Profundidade) em Zig — Implementação e Explicação

A DFS em Zig (Depth-First Search ou busca em profundidade) percorre um grafo avançando por um caminho até não encontrar outro vizinho não visitado. Nesse ponto, o algoritmo retrocede e continua pelos ramos restantes. Com uma lista de adjacência, sua complexidade é O(V + E): cada vértice é visitado uma vez e cada aresta é examinada.

A implementação pode usar a pilha de chamadas, na versão recursiva, ou uma pilha explícita, na versão iterativa. Para grafos grandes ou com caminhos muito profundos, a versão iterativa é normalmente a escolha mais segura.

Como a busca em profundidade funciona

O algoritmo mantém um conjunto de vértices visitados para não entrar em repetição. A partir de uma origem:

1. coloca o vértice atual entre os visitados;
2. registra ou processa esse vértice;
3. escolhe um vizinho ainda não visitado;
4. repete o processo a partir do vizinho;
5. quando não há como avançar, retrocede ao vértice anterior.

Considere este grafo não direcionado:

    0 --- 1 --- 3
    |     |
    2 --- 4 --- 5

Uma DFS iniciada em 0, respeitando a ordem das listas de adjacência, pode produzir:

0 → 1 → 3 → 4 → 2 → 5

Outra ordem também pode estar correta. Se os vizinhos de 0 forem armazenados como [2, 1] em vez de [1, 2], a busca seguirá um ramo diferente primeiro. A DFS não define uma ordem única sem que a aplicação também defina como os vizinhos são ordenados.

Representando o grafo com lista de adjacência

Uma lista de adjacência guarda, para cada vértice, a coleção de seus vizinhos. Ela usa espaço O(V + E) e é mais adequada que uma matriz de adjacência para grafos esparsos.

const std = @import("std");
const Allocator = std.mem.Allocator;

const Grafo = struct {
    adjacencia: []std.ArrayList(usize),
    allocator: Allocator,

    pub fn init(allocator: Allocator, numero_de_vertices: usize) !Grafo {
        const adjacencia = try allocator.alloc(
            std.ArrayList(usize),
            numero_de_vertices,
        );
        errdefer allocator.free(adjacencia);

        for (adjacencia) |*vizinhos| {
            vizinhos.* = std.ArrayList(usize).init(allocator);
        }

        return .{
            .adjacencia = adjacencia,
            .allocator = allocator,
        };
    }

    pub fn deinit(self: *Grafo) void {
        for (self.adjacencia) |*vizinhos| {
            vizinhos.deinit();
        }
        self.allocator.free(self.adjacencia);
    }

    pub fn adicionarAresta(
        self: *Grafo,
        origem: usize,
        destino: usize,
    ) !void {
        if (origem >= self.adjacencia.len or destino >= self.adjacencia.len) {
            return error.VerticeInvalido;
        }

        try self.adjacencia[origem].append(destino);
        errdefer _ = self.adjacencia[origem].pop();
        try self.adjacencia[destino].append(origem);
    }

    pub fn adicionarArestaDirecionada(
        self: *Grafo,
        origem: usize,
        destino: usize,
    ) !void {
        if (origem >= self.adjacencia.len or destino >= self.adjacencia.len) {
            return error.VerticeInvalido;
        }

        try self.adjacencia[origem].append(destino);
    }
};

adicionarAresta insere os dois sentidos de uma aresta não direcionada. Já adicionarArestaDirecionada insere apenas origem → destino. Essa distinção importa, inclusive, na detecção de ciclos.

O errdefer da aresta não direcionada desfaz a primeira inserção se a segunda falhar por falta de memória. Assim, o grafo não fica parcialmente atualizado.

DFS recursiva em Zig

A versão recursiva traduz diretamente a definição do algoritmo:

fn visitarRecursivamente(
    grafo: *const Grafo,
    vertice: usize,
    visitado: []bool,
    ordem: *std.ArrayList(usize),
) !void {
    visitado[vertice] = true;
    try ordem.append(vertice);

    for (grafo.adjacencia[vertice].items) |vizinho| {
        if (!visitado[vizinho]) {
            try visitarRecursivamente(grafo, vizinho, visitado, ordem);
        }
    }
}

pub fn dfsRecursiva(
    allocator: Allocator,
    grafo: *const Grafo,
    origem: usize,
) ![]usize {
    if (origem >= grafo.adjacencia.len) return error.VerticeInvalido;

    const visitado = try allocator.alloc(bool, grafo.adjacencia.len);
    defer allocator.free(visitado);
    @memset(visitado, false);

    var ordem = std.ArrayList(usize).init(allocator);
    errdefer ordem.deinit();

    try visitarRecursivamente(grafo, origem, visitado, &ordem);
    return try ordem.toOwnedSlice();
}

É importante propagar o erro de ordem.append com try. Ignorar uma falha de alocação pode devolver uma travessia incompleta como se ela estivesse correta.

Vantagens e limites da versão recursiva

A DFS recursiva é curta e deixa a relação entre algoritmo e código muito clara. Entretanto, cada avanço consome um frame da pilha de chamadas. Um grafo em forma de caminho com centenas de milhares de vértices pode causar stack overflow, mesmo que exista memória suficiente no heap.

Use a recursiva para ensino, grafos pequenos ou quando a profundidade máxima é conhecida. Para entrada externa ou grafos potencialmente profundos, prefira a implementação iterativa.

DFS iterativa com pilha explícita

A versão iterativa guarda os próximos vértices em uma ArrayList, usando o final da lista como topo da pilha:

pub fn dfsIterativa(
    allocator: Allocator,
    grafo: *const Grafo,
    origem: usize,
) ![]usize {
    if (origem >= grafo.adjacencia.len) return error.VerticeInvalido;

    const visitado = try allocator.alloc(bool, grafo.adjacencia.len);
    defer allocator.free(visitado);
    @memset(visitado, false);

    var ordem = std.ArrayList(usize).init(allocator);
    errdefer ordem.deinit();

    var pilha = std.ArrayList(usize).init(allocator);
    defer pilha.deinit();
    try pilha.append(origem);

    while (pilha.items.len > 0) {
        const vertice = pilha.pop();

        if (visitado[vertice]) continue;
        visitado[vertice] = true;
        try ordem.append(vertice);

        // Empilha em ordem reversa para visitar primeiro o vizinho
        // que aparece antes na lista de adjacência.
        var i = grafo.adjacencia[vertice].items.len;
        while (i > 0) {
            i -= 1;
            const vizinho = grafo.adjacencia[vertice].items[i];
            if (!visitado[vizinho]) {
                try pilha.append(vizinho);
            }
        }
    }

    return try ordem.toOwnedSlice();
}

Um vértice pode entrar na pilha mais de uma vez quando vários vizinhos apontam para ele. Isso não compromete a correção porque a verificação ocorre logo após o pop. Marcar o vértice apenas no momento do processamento também preserva a ordem esperada para esta implementação.

Se o objetivo for reduzir inserções duplicadas, você pode marcar o vértice ao empilhá-lo. Essa variação muda detalhes da ordem e exige que a origem seja marcada antes do laço.

Exemplo completo de uso

pub fn main() !void {
    const stdout = std.io.getStdOut().writer();

    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();

    var grafo = try Grafo.init(allocator, 6);
    defer grafo.deinit();

    try grafo.adicionarAresta(0, 1);
    try grafo.adicionarAresta(0, 2);
    try grafo.adicionarAresta(1, 3);
    try grafo.adicionarAresta(1, 4);
    try grafo.adicionarAresta(2, 4);
    try grafo.adicionarAresta(4, 5);

    const ordem = try dfsIterativa(allocator, &grafo, 0);
    defer allocator.free(ordem);

    try stdout.print("DFS:", .{});
    for (ordem) |vertice| {
        try stdout.print(" {d}", .{vertice});
    }
    try stdout.print("\n", .{});
}

Para a ordem de inserção acima, a saída é:

DFS: 0 1 3 4 2 5

Como percorrer componentes desconectados

Uma DFS iniciada em um único vértice visita apenas o componente alcançável a partir dele. Para percorrer o grafo inteiro, faça um laço sobre todos os vértices e inicie outra DFS sempre que encontrar um vértice ainda não visitado:

var vertice: usize = 0;
while (vertice < grafo.adjacencia.len) : (vertice += 1) {
    if (!visitado[vertice]) {
        try visitarRecursivamente(grafo, vertice, visitado, &ordem);
        componentes += 1;
    }
}

A quantidade de vezes que uma nova busca é iniciada é o número de componentes conexos de um grafo não direcionado.

Detecção de ciclos: direcionado não é igual a não direcionado

Em um grafo direcionado, é comum usar três cores:

• branco: ainda não visitado;
• cinza: está na pilha ativa da DFS;
• preto: processamento concluído.

Uma aresta para um vértice cinza indica um ciclo direcionado. Em um grafo não direcionado, porém, a aresta de volta para o pai é normal e não representa um ciclo. Nesse caso, a função deve receber o pai atual e ignorar essa aresta.

Essa diferença evita um erro frequente: aplicar diretamente a regra das três cores a um grafo não direcionado e concluir que toda aresta possui um ciclo por causa do retorno ao vértice anterior.

Para ordenação topológica, use a estratégia de cores somente em um DAG, um grafo direcionado acíclico. Veja a implementação específica de ordenação topológica em Zig.

Testando a implementação

Testes devem verificar a ordem prevista para a ordem de adjacência escolhida, casos de borda e erros de entrada:

test "DFS iterativa visita todos os vertices alcancaveis" {
    const allocator = std.testing.allocator;

    var grafo = try Grafo.init(allocator, 4);
    defer grafo.deinit();

    try grafo.adicionarAresta(0, 1);
    try grafo.adicionarAresta(0, 2);
    try grafo.adicionarAresta(1, 3);

    const ordem = try dfsIterativa(allocator, &grafo, 0);
    defer allocator.free(ordem);

    try std.testing.expectEqualSlices(
        usize,
        &.{ 0, 1, 3, 2 },
        ordem,
    );
}

test "DFS rejeita origem inexistente" {
    const allocator = std.testing.allocator;

    var grafo = try Grafo.init(allocator, 2);
    defer grafo.deinit();

    try std.testing.expectError(
        error.VerticeInvalido,
        dfsIterativa(allocator, &grafo, 2),
    );
}

Usar std.testing.allocator ajuda a detectar vazamentos durante os testes. Execute o arquivo com:

zig test dfs.zig

Complexidade da DFS

A análise pressupõe uma lista de adjacência. Em uma matriz de adjacência, é necessário examinar uma linha de V posições para cada vértice, levando o percurso a O(V²) mesmo quando há poucas arestas.

DFS ou BFS: qual usar?

A BFS em Zig usa uma fila e visita primeiro todos os vértices a uma aresta da origem. A DFS usa uma pilha e prioriza profundidade. Nenhuma é universalmente melhor: a estrutura do problema determina a escolha.

Aplicações práticas

A busca em profundidade aparece em diversas tarefas:

• componentes conexos em redes e mapas;
• detecção de ciclos em dependências;
• ordenação topológica de tarefas;
• resolução de labirintos e problemas de backtracking;
• análise de dependências de módulos e pacotes;
• pontes e vértices de articulação em redes;
• componentes fortemente conexos com Tarjan ou Kosaraju;
• árvores de sintaxe e sistemas de arquivos, quando a estrutura pode ser modelada como árvore ou grafo.

Erros comuns

Não manter o vetor de visitados

Sem visitado, um grafo com ciclo pode repetir os mesmos vértices indefinidamente. Mesmo em um DAG, caminhos convergentes podem processar o mesmo nó várias vezes.

Engolir erros de alocação

Evite catch {} ao adicionar um vértice ao resultado. Propague a falha com try e use errdefer para liberar estruturas parcialmente construídas.

Confundir ordem correta com ordem única

A ordem depende da sequência dos vizinhos. Se uma aplicação precisa de saída determinística independente da inserção, ordene as listas de adjacência antes da busca.

Usar recursão com profundidade não controlada

Um grafo pequeno em número de arestas ainda pode formar um caminho muito profundo. Quando os dados vêm do usuário, de arquivos ou da rede, a pilha explícita oferece um limite operacional mais previsível.

Detectar ciclos sem considerar o tipo de grafo

No grafo direcionado, uma aresta para um vértice cinza indica ciclo. No não direcionado, é preciso ignorar a aresta que volta ao pai. Misturar as duas regras produz falsos positivos.

Resumo

Use DFS quando precisar explorar um grafo por profundidade, identificar componentes, detectar ciclos ou construir uma ordenação topológica. A versão recursiva é a mais didática; a iterativa é mais robusta para profundidades grandes. Em ambas, mantenha o vetor de visitados, propague erros e defina explicitamente se o grafo é direcionado.

Recursos relacionados