BFS em Zig: Busca em Largura, Menor Caminho e Fila

A BFS em Zig (Breadth-First Search ou busca em largura) percorre um grafo por níveis: primeiro visita a origem, depois todos os vértices a uma aresta dela, em seguida os vértices a duas arestas e assim por diante. Com lista de adjacência, sua complexidade é O(V + E). Além de percorrer o grafo, BFS encontra o menor caminho em número de arestas quando não há pesos ou quando todas as arestas têm o mesmo custo.

A recomendação direta é: use BFS para labirintos sem custos diferentes, redes de contatos, dependências por nível, distância mínima em movimentos uniformes e qualquer grafo não ponderado. Use Dijkstra em Zig quando os custos forem não negativos, mas variarem entre arestas. Para explorar profundamente um ramo, detectar ciclos ou produzir uma ordenação topológica, compare com DFS em Zig.

Resposta rápida

A propriedade mais importante é a ordem FIFO: o primeiro vértice inserido é o primeiro removido. Isso garante que todos os vértices de distância d sejam processados antes dos vértices de distância d + 1.

Como a busca em largura funciona

A BFS mantém três informações:

1. uma fila de vértices descobertos, mas ainda não processados;
2. uma marca de visitado ou uma distância para evitar inserções repetidas;
3. opcionalmente, o predecessor usado para chegar a cada vértice.

O algoritmo começa colocando a origem na fila com distância zero. Enquanto a fila não estiver vazia, remove o próximo vértice e examina seus vizinhos. Cada vizinho ainda não descoberto recebe distância igual à distância atual mais um, guarda o vértice atual como predecessor e entra no final da fila.

distância[origem] = 0
fila.adicionar(origem)

while fila não vazia:
    atual = fila.remover()
    para cada vizinho de atual:
        se vizinho ainda não foi descoberto:
            distância[vizinho] = distância[atual] + 1
            predecessor[vizinho] = atual
            fila.adicionar(vizinho)

Marcar o vizinho no momento em que ele entra na fila é essencial. Se a marcação ocorrer apenas quando ele sair, vários vértices podem adicionar o mesmo vizinho, desperdiçando memória e processamento.

Exemplo passo a passo

Considere o grafo não direcionado:

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

Com origem 0, o processamento por níveis é:

nível 0: 0
nível 1: 1, 2
nível 2: 3, 4
nível 3: 5

Uma ordem possível é 0, 1, 2, 3, 4, 5. A distância mínima até 5 é três arestas. Dependendo da ordem dos vizinhos, a rota reconstruída pode ser 0 → 1 → 4 → 5 ou 0 → 2 → 4 → 5. As duas são mínimas.

BFS garante a menor quantidade de arestas, não necessariamente uma rota única. Se o produto precisa desempatar por ordem alfabética, menor identificador ou outro critério, ordene as listas de adjacência antes da busca.

Representando o grafo em Zig

Para manter o exemplo focado no algoritmo, o grafo será recebido como um slice de slices. Cada posição representa um vértice e contém seus vizinhos:

const adjacencia = [_][]const usize{
    &.{ 1, 2 },       // vizinhos de 0
    &.{ 0, 3, 4 },    // vizinhos de 1
    &.{ 0, 4 },       // vizinhos de 2
    &.{ 1 },          // vizinhos de 3
    &.{ 1, 2, 5 },    // vizinhos de 4
    &.{ 4 },          // vizinhos de 5
};

Como o exemplo é não direcionado, cada ligação aparece nos dois sentidos. A aresta 0 — 1, por exemplo, exige 1 na lista de 0 e 0 na lista de 1. Em um grafo direcionado, inclua somente o sentido permitido.

Uma lista de adjacência ocupa O(V + E) e evita examinar posições vazias. Em uma matriz de adjacência, BFS precisa percorrer uma linha de V posições para cada vértice removido da fila, levando a O(V²), mesmo em grafos esparsos.

Implementação completa de BFS em Zig

A implementação abaixo aloca distâncias, predecessores e uma fila com capacidade para V vértices. A fila pode ter tamanho fixo porque cada vértice é descoberto e inserido no máximo uma vez.

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

const ResultadoBfs = struct {
    distancias: []?usize,
    predecessores: []?usize,
    allocator: Allocator,

    pub fn deinit(self: *ResultadoBfs) void {
        self.allocator.free(self.distancias);
        self.allocator.free(self.predecessores);
    }
};

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

    const distancias = try allocator.alloc(?usize, adjacencia.len);
    errdefer allocator.free(distancias);

    const predecessores = try allocator.alloc(?usize, adjacencia.len);
    errdefer allocator.free(predecessores);

    const fila = try allocator.alloc(usize, adjacencia.len);
    defer allocator.free(fila);

    @memset(distancias, null);
    @memset(predecessores, null);

    var inicio: usize = 0;
    var fim: usize = 0;

    distancias[origem] = 0;
    fila[fim] = origem;
    fim += 1;

    while (inicio < fim) {
        const atual = fila[inicio];
        inicio += 1;

        for (adjacencia[atual]) |vizinho| {
            if (vizinho >= adjacencia.len) {
                return error.VerticeInvalido;
            }
            if (distancias[vizinho] != null) continue;

            distancias[vizinho] = distancias[atual].? + 1;
            predecessores[vizinho] = atual;
            fila[fim] = vizinho;
            fim += 1;
        }
    }

    return .{
        .distancias = distancias,
        .predecessores = predecessores,
        .allocator = allocator,
    };
}

distancias usa ?usize: null significa que o vértice ainda não foi alcançado; um valor numérico representa a menor quantidade de arestas desde a origem. Isso evita escolher um inteiro sentinela e também funciona como marca de visitado.

O errdefer libera as alocações anteriores se uma etapa posterior falhar. A fila é temporária e sempre é liberada antes do retorno. Já distâncias e predecessores pertencem ao resultado; por isso, o chamador precisa executar deinit.

Por que a fila simples não precisa ser circular

Uma fila de produção costuma reutilizar o espaço removido com índices circulares. Nesta BFS, porém, cada vértice entra exatamente uma vez. Portanto, no máximo V posições são escritas durante toda a execução, e os índices inicio e fim só avançam.

Essa escolha torna o exemplo menor e elimina operações de módulo. Ela não serve como fila genérica para um processo que adiciona e remove itens indefinidamente, mas é correta para este algoritmo sob o contrato de descoberta única.

A condição que protege esse contrato é:

if (distancias[vizinho] != null) continue;

A distância é atribuída antes da inserção. Assim, duas arestas examinadas em sequência não conseguem inserir o mesmo vértice.

Reconstruindo o menor caminho

O array de predecessores permite recuperar uma rota mínima. Comece no destino, siga os predecessores até a origem e escreva os vértices em ordem inversa. A função abaixo usa um buffer fornecido pelo chamador, evitando uma nova alocação:

pub fn reconstruirCaminho(
    predecessores: []const ?usize,
    origem: usize,
    destino: usize,
    buffer: []usize,
) !?[]usize {
    if (origem >= predecessores.len or destino >= predecessores.len) {
        return error.VerticeInvalido;
    }
    if (buffer.len < predecessores.len) return error.BufferInsuficiente;

    var quantidade: usize = 0;
    var atual: ?usize = destino;

    while (atual) |vertice| {
        if (quantidade == predecessores.len) {
            return error.CadeiaDePredecessoresInvalida;
        }

        buffer[quantidade] = vertice;
        quantidade += 1;

        if (vertice == origem) break;
        atual = predecessores[vertice];
    }

    if (quantidade == 0 or buffer[quantidade - 1] != origem) {
        return null;
    }

    std.mem.reverse(usize, buffer[0..quantidade]);
    return buffer[0..quantidade];
}

Um destino inalcançável tem predecessor null sem que a cadeia chegue à origem; nesse caso, a função retorna null. Índice inválido, buffer pequeno e cadeia corrompida são erros separados. Essa distinção deixa a API mais clara para o chamador.

Teste completo

O teste a seguir verifica distâncias, vértice desconectado e reconstrução da rota:

test "BFS calcula distancias e reconstrói caminho" {
    const allocator = std.testing.allocator;
    const adjacencia = [_][]const usize{
        &.{ 1, 2 },
        &.{ 0, 3, 4 },
        &.{ 0, 4 },
        &.{ 1 },
        &.{ 1, 2, 5 },
        &.{ 4 },
        &.{}, // vértice 6 desconectado
    };

    var resultado = try bfs(allocator, &adjacencia, 0);
    defer resultado.deinit();

    try std.testing.expectEqual(@as(?usize, 0), resultado.distancias[0]);
    try std.testing.expectEqual(@as(?usize, 1), resultado.distancias[1]);
    try std.testing.expectEqual(@as(?usize, 2), resultado.distancias[4]);
    try std.testing.expectEqual(@as(?usize, 3), resultado.distancias[5]);
    try std.testing.expectEqual(@as(?usize, null), resultado.distancias[6]);

    var buffer: [7]usize = undefined;
    const caminho = (try reconstruirCaminho(
        resultado.predecessores,
        0,
        5,
        &buffer,
    )).?;

    try std.testing.expectEqualSlices(
        usize,
        &.{ 0, 1, 4, 5 },
        caminho,
    );
}

Execute com:

zig test bfs.zig

O caminho esperado depende da ordem da adjacência. Como 1 aparece antes de 2 na lista de 0, o vértice 4 é descoberto por 1, produzindo 0 → 1 → 4 → 5. Se a ordem mudar, 0 → 2 → 4 → 5 também será uma resposta mínima válida.

BFS encontra menor caminho por quê?

Quando um vértice de distância d é removido, todos os vértices de distância menor já foram processados. Seus vizinhos ainda não descobertos recebem distância d + 1. Não pode existir uma rota com menos arestas até esses vizinhos, pois essa rota teria de passar por um nível anterior que já foi examinado.

Essa prova depende de cada aresta contribuir com o mesmo custo. Se uma aresta custa 20 e outra custa 1, contar ambas como um único passo não representa o custo real. Nesse cenário, use Dijkstra para pesos não negativos ou Bellman-Ford quando pesos negativos forem possíveis.

BFS, DFS ou Dijkstra?

BFS e DFS têm a mesma complexidade O(V + E) com lista de adjacência, mas sua ordem de exploração muda o que pode ser garantido. DFS pode encontrar algum caminho rapidamente, porém o primeiro caminho encontrado não precisa ser o menor. BFS preserva a ordem por níveis e, por isso, resolve a distância mínima sem pesos.

Grafos direcionados e desconectados

A implementação funciona em grafos direcionados sem alterações. A diferença está apenas na construção das listas. Se 0 aponta para 1, mas 1 não aponta para 0, então uma busca iniciada em 1 não atravessa essa ligação ao contrário.

Em um grafo desconectado, BFS visita somente o componente alcançável a partir da origem. Os demais vértices continuam com distância null. Para percorrer o grafo inteiro ou contar componentes conexos, mantenha um array global de descobertos e inicie uma nova BFS em cada vértice ainda não visitado.

Em grafos direcionados, repetir a busca dessa forma produz uma floresta de alcance, mas não calcula componentes fortemente conexos. Para isso, use algoritmos específicos como Tarjan ou Kosaraju.

Aplicações práticas

A busca em largura aparece em problemas comuns de software:

• labirintos e grids, quando cada movimento vale um passo;
• graus de separação em redes sociais;
• dependências por nível, como etapas liberadas após pré-requisitos;
• broadcast em redes, simulando ondas a partir de uma origem;
• web crawling limitado por profundidade;
• menor sequência de transformações, quando cada operação tem custo uniforme;
• árvores, para travessia por nível;
• matching bipartido, como parte do Hopcroft-Karp;
• fluxo máximo, como construção de níveis no Dinic;
• ordenação topológica, por meio da fila do algoritmo de Kahn.

Em um grid, cada célula pode ser convertida em vértice, e movimentos válidos formam arestas. Para evitar construir explicitamente todas as listas, gere os vizinhos sob demanda — cima, baixo, esquerda e direita — durante o processamento.

Erros comuns

Marcar o vértice tarde demais

Marque como descoberto antes de adicionar à fila. Marcar apenas na remoção permite duplicatas e pode estourar uma fila dimensionada para V.

Usar BFS com pesos diferentes

BFS minimiza arestas, não a soma de custos arbitrários. Uma rota com duas arestas caras pode ser pior que outra com quatro arestas baratas.

Esquecer o sentido das arestas

Uma ligação não direcionada precisa ser inserida nas duas listas. Se apenas um sentido for criado, os resultados dependem da origem e podem parecer incompletos.

Confundir distância nula com zero

Somente a origem tem distância zero. null significa inalcançável ou ainda não descoberto. Não inicialize todas as distâncias com zero.

Exigir uma rota mínima específica

Pode haver várias rotas com a mesma quantidade de arestas. Se o teste compara a sequência exata, ele também precisa controlar a ordem das listas de adjacência.

Não validar os vizinhos

Dados vindos de arquivo, rede ou usuário podem conter índices fora do intervalo. A implementação valida cada vizinho antes de acessar distancias[vizinho].

Checklist para uso em produção

• represente grafos esparsos com lista de adjacência;
• marque o vértice no momento da inserção na fila;
• valide a origem e todos os índices de vizinhos;
• use ?usize ou outro estado explícito para inalcançável;
• guarde predecessores somente se a rota for necessária;
• documente a regra de desempate entre caminhos mínimos;
• trate componentes desconectados conscientemente;
• não use BFS se os custos das arestas forem diferentes;
• teste grafo vazio, vértice isolado, ciclos e múltiplas rotas;
• meça memória se V puder ser muito grande.

Conclusão

BFS é o algoritmo padrão para percorrer grafos por níveis e encontrar o menor caminho em número de arestas. Uma implementação robusta em Zig combina lista de adjacência, fila FIFO, distâncias opcionais, predecessores e validação de índices. Com essas estruturas, o custo permanece O(V + E) e a propriedade da memória fica explícita.

A regra de escolha é simples: use BFS quando cada transição tiver o mesmo custo; use Dijkstra quando os custos não negativos variarem; use Bellman-Ford se valores negativos forem possíveis. Para aprofundar ramos, detectar ciclos e trabalhar com ordenação topológica, consulte a implementação de DFS em Zig. Para revisar slices, allocators e filas, veja também o guia de estruturas de dados em Zig.