--- title: "BFS (Busca em Largura) em Zig — Implementação e Explicação" url: "https://ziglang.com.br/algoritmos/bfs-busca-em-largura-em-zig-implementa%C3%A7%C3%A3o-e-explica%C3%A7%C3%A3o/" markdown_url: "https://ziglang.com.br/algoritmos/bfs-busca-em-largura-em-zig-implementa%C3%A7%C3%A3o-e-explica%C3%A7%C3%A3o.MD" description: "Aprenda o algoritmo BFS (Busca em Largura) implementado em Zig. Percurso nível a nível em grafos com código funcional e análise de complexidade." date: "2026-02-21" author: "Zig Brasil" --- # BFS (Busca em Largura) em Zig — Implementação e Explicação Aprenda o algoritmo BFS (Busca em Largura) implementado em Zig. Percurso nível a nível em grafos com código funcional e análise de complexidade. # BFS (Busca em Largura) em Zig — Implementação e Explicação A **BFS** (Breadth-First Search / Busca em Largura) é um algoritmo fundamental para percorrer ou buscar em grafos e árvores. Ela explora todos os vizinhos de um vértice antes de avançar para os vizinhos dos vizinhos, percorrendo o grafo **nível a nível**. ## Como Funciona 1. Coloque o vértice inicial em uma **fila** e marque como visitado 2. Enquanto a fila não estiver vazia: - Remova o primeiro vértice da fila - Processe-o - Adicione todos os vizinhos não visitados à fila e marque-os como visitados ### Visualização do Processo ``` Grafo: 0 --- 1 --- 3 | | 2 --- 4 --- 5 BFS a partir do vértice 0: Fila: [0] Visitados: {0} Processa 0 → vizinhos: 1, 2 Fila: [1, 2] Visitados: {0, 1, 2} Processa 1 → vizinhos: 0(✓), 3, 4 Fila: [2, 3, 4] Visitados: {0, 1, 2, 3, 4} Processa 2 → vizinhos: 0(✓), 4(✓) Fila: [3, 4] Visitados: {0, 1, 2, 3, 4} Processa 3 → vizinhos: 1(✓) Fila: [4] Visitados: {0, 1, 2, 3, 4} Processa 4 → vizinhos: 1(✓), 2(✓), 5 Fila: [5] Visitados: {0, 1, 2, 3, 4, 5} Processa 5 → vizinhos: 4(✓) Fila: [] Ordem de visita: 0 → 1 → 2 → 3 → 4 → 5 Níveis: 0 1 1 2 2 3 ``` ## Implementação em Zig ```zig const std = @import("std"); const Allocator = std.mem.Allocator; /// Grafo representado por lista de adjacência. const Grafo = struct { adjacencia: []std.ArrayList(u32), num_vertices: u32, allocator: Allocator, pub fn init(allocator: Allocator, num_vertices: u32) !Grafo { const adj = try allocator.alloc(std.ArrayList(u32), num_vertices); for (adj) |*lista| { lista.* = std.ArrayList(u32).init(allocator); } return Grafo{ .adjacencia = adj, .num_vertices = num_vertices, .allocator = allocator, }; } pub fn deinit(self: *Grafo) void { for (self.adjacencia) |*lista| lista.deinit(); self.allocator.free(self.adjacencia); } pub fn addAresta(self: *Grafo, u: u32, v: u32) !void { try self.adjacencia[u].append(v); try self.adjacencia[v].append(u); // grafo não-direcionado } }; /// BFS que retorna a ordem de visita e as distâncias. pub fn bfs( allocator: Allocator, grafo: *const Grafo, origem: u32, ) !struct { ordem: []u32, distancia: []i32, pai: []i32 } { const n = grafo.num_vertices; // Arrays de controle const visitado = try allocator.alloc(bool, n); defer allocator.free(visitado); @memset(visitado, false); const distancia = try allocator.alloc(i32, n); @memset(distancia, -1); const pai = try allocator.alloc(i32, n); @memset(pai, -1); var ordem = std.ArrayList(u32).init(allocator); // Fila para BFS var fila = std.ArrayList(u32).init(allocator); defer fila.deinit(); // Inicializa com a origem try fila.append(origem); visitado[origem] = true; distancia[origem] = 0; while (fila.items.len > 0) { // Remove o primeiro da fila (FIFO) const atual = fila.orderedRemove(0); try ordem.append(atual); // Visita todos os vizinhos for (grafo.adjacencia[atual].items) |vizinho| { if (!visitado[vizinho]) { visitado[vizinho] = true; distancia[vizinho] = distancia[atual] + 1; pai[vizinho] = @intCast(atual); try fila.append(vizinho); } } } return .{ .ordem = try ordem.toOwnedSlice(), .distancia = distancia, .pai = pai, }; } /// Reconstrói o caminho mais curto da origem até o destino. pub fn reconstruirCaminho( allocator: Allocator, pai: []const i32, destino: u32, ) ![]u32 { var caminho = std.ArrayList(u32).init(allocator); var atual: i32 = @intCast(destino); while (atual != -1) { try caminho.insert(0, @intCast(@as(u32, @intCast(atual)))); atual = pai[@intCast(@as(u32, @intCast(atual)))]; } return caminho.toOwnedSlice(); } 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.addAresta(0, 1); try grafo.addAresta(0, 2); try grafo.addAresta(1, 3); try grafo.addAresta(1, 4); try grafo.addAresta(2, 4); try grafo.addAresta(4, 5); const resultado = try bfs(allocator, &grafo, 0); defer allocator.free(resultado.ordem); defer allocator.free(resultado.distancia); defer allocator.free(resultado.pai); try stdout.print("Ordem BFS: ", .{}); for (resultado.ordem) |v| try stdout.print("{d} ", .{v}); try stdout.print("\n", .{}); try stdout.print("Distâncias: ", .{}); for (resultado.distancia, 0..) |d, i| { try stdout.print("{d}→{d} ", .{ i, d }); } try stdout.print("\n", .{}); // Caminho mais curto de 0 a 5 const caminho = try reconstruirCaminho(allocator, resultado.pai, 5); defer allocator.free(caminho); try stdout.print("Caminho 0→5: ", .{}); for (caminho) |v| try stdout.print("{d} ", .{v}); try stdout.print("\n", .{}); } ``` ## Análise de Complexidade | Caso | Tempo | Espaço | |------|-------|--------| | **Todos os casos** | O(V + E) | O(V) | Onde V = número de vértices e E = número de arestas. ## Aplicações - **Caminho mais curto**: em grafos sem peso, BFS encontra o caminho mais curto - **Teste de bipartição**: verifica se o grafo é bipartido - **Componentes conexos**: encontra todos os componentes - **Nível de cada vértice**: distância mínima de arestas - **Web crawling**: exploração de páginas nível a nível ## BFS vs DFS | Aspecto | BFS | [DFS](/algoritmos/dfs-busca-profundidade/) | |---------|-----|-----| | Estrutura | Fila (FIFO) | Pilha (LIFO) | | Percurso | Nível a nível | Ramo a ramo | | Caminho curto | Sim (sem peso) | Não garante | | Memória | O(largura máxima) | O(profundidade) | | Uso | Caminho curto, nível | Ciclos, topológica | ## Recursos Relacionados - [DFS — Busca em Profundidade](/algoritmos/dfs-busca-profundidade/) — Percurso alternativo - [Dijkstra](/algoritmos/dijkstra/) — Caminho mais curto com pesos - [Grafo — Lista de Adjacência](/estruturas-dados/grafo-lista-adjacencia/) — Representação usada - [Fila](/estruturas-dados/fila/) — Estrutura base da BFS - [Receitas de Grafos](/receitas/) — Exemplos práticos