--- title: "BFS em Zig: Busca em Largura, Menor Caminho e Fila" url: "https://ziglang.com.br/algoritmos/bfs-busca-largura/" markdown_url: "https://ziglang.com.br/algoritmos/bfs-busca-largura.MD" description: "Implemente BFS em Zig com lista de adjacência, fila, distâncias e predecessores para percorrer grafos e encontrar caminhos mínimos sem pesos." date: "2026-08-23" author: "Zig Brasil" --- # BFS em Zig: Busca em Largura, Menor Caminho e Fila Implemente BFS em Zig com lista de adjacência, fila, distâncias e predecessores para percorrer grafos e encontrar caminhos mínimos sem pesos. # 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](/algoritmos/dijkstra/) 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](/algoritmos/dfs-busca-profundidade/). ## Resposta rápida | Pergunta | Resposta | |---|---| | Como BFS percorre o grafo? | por níveis de distância a partir da origem | | Estrutura principal | fila FIFO | | Complexidade com lista de adjacência | O(V + E) | | Espaço auxiliar | O(V) | | Encontra menor caminho? | sim, em grafos sem pesos ou com custo uniforme | | Grafo desconectado | visita apenas o componente da origem | | Como recuperar a rota? | seguindo o array de predecessores | | Alternativa para pesos diferentes | Dijkstra | | Alternativa para busca em profundidade | DFS | 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. ```text 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: ```text 0 --- 1 --- 3 | | 2 --- 4 --- 5 ``` Com origem `0`, o processamento por níveis é: ```text 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: ```zig 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. ```zig 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 é: ```zig 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: ```zig 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: ```zig 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: ```bash 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](/algoritmos/dijkstra/) para pesos não negativos ou [Bellman-Ford](/algoritmos/bellman-ford/) quando pesos negativos forem possíveis. ## BFS, DFS ou Dijkstra? | Situação | Algoritmo indicado | |---|---| | menor número de passos em grafo sem pesos | BFS | | todas as arestas têm o mesmo custo | BFS | | explorar profundamente e retroceder | DFS | | detectar ciclos e ordenar um DAG | DFS ou Kahn | | pesos não negativos diferentes | Dijkstra | | pesos negativos | Bellman-Ford | | distâncias entre todos os pares | Floyd-Warshall | 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](/algoritmos/dijkstra/) quando os custos não negativos variarem; use [Bellman-Ford](/algoritmos/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](/algoritmos/dfs-busca-profundidade/). Para revisar slices, allocators e filas, veja também o guia de [estruturas de dados em Zig](/estruturas-dados/).