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

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", .{});
}