Grafo não-direcionado com 5 vértices:

    0 --- 1 --- 2
          |   /
          3 - 4

Matriz de Adjacência:
      0  1  2  3  4
  0 [ 0  1  0  0  0 ]
  1 [ 1  0  1  1  0 ]
  2 [ 0  1  0  0  1 ]
  3 [ 0  1  0  0  1 ]
  4 [ 0  0  1  1  0 ]

Simétrica para grafos não-direcionados.
Espaço: O(V^2)

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

/// Grafo com matriz de adjacência alocada dinamicamente.
pub fn GrafoMatriz(comptime direcionado: bool) type {
    return struct {
        const Self = @This();

        matriz: [][]u8,
        num_vertices: u32,
        num_arestas: u32,
        allocator: Allocator,

        pub fn init(allocator: Allocator, num_vertices: u32) !Self {
            const n: usize = num_vertices;
            const matriz = try allocator.alloc([]u8, n);
            for (matriz) |*linha| {
                linha.* = try allocator.alloc(u8, n);
                @memset(linha.*, 0);
            }
            return .{
                .matriz = matriz,
                .num_vertices = num_vertices,
                .num_arestas = 0,
                .allocator = allocator,
            };
        }

        pub fn deinit(self: *Self) void {
            for (self.matriz) |linha| {
                self.allocator.free(linha);
            }
            self.allocator.free(self.matriz);
        }

        /// Adiciona aresta entre u e v — O(1).
        pub fn adicionarAresta(self: *Self, u: u32, v: u32) void {
            self.matriz[u][v] = 1;
            if (!direcionado) {
                self.matriz[v][u] = 1;
            }
            self.num_arestas += 1;
        }

        /// Remove aresta entre u e v — O(1).
        pub fn removerAresta(self: *Self, u: u32, v: u32) void {
            if (self.matriz[u][v] == 1) {
                self.matriz[u][v] = 0;
                if (!direcionado) {
                    self.matriz[v][u] = 0;
                }
                self.num_arestas -= 1;
            }
        }

        /// Verifica se existe aresta — O(1).
        pub fn temAresta(self: *const Self, u: u32, v: u32) bool {
            return self.matriz[u][v] == 1;
        }

        /// Grau de um vértice — O(V).
        pub fn grau(self: *const Self, v: u32) u32 {
            var g: u32 = 0;
            for (self.matriz[v]) |val| {
                g += val;
            }
            return g;
        }

        /// BFS — Busca em largura.
        pub fn bfs(self: *const Self, inicio: u32, allocator: Allocator) ![]u32 {
            var visitado = try allocator.alloc(bool, self.num_vertices);
            defer allocator.free(visitado);
            @memset(visitado, false);

            var fila = std.ArrayList(u32).init(allocator);
            defer fila.deinit();
            var ordem = std.ArrayList(u32).init(allocator);

            visitado[inicio] = true;
            try fila.append(inicio);

            while (fila.items.len > 0) {
                const atual = fila.orderedRemove(0);
                try ordem.append(atual);

                for (0..self.num_vertices) |v| {
                    if (self.matriz[atual][v] == 1 and !visitado[v]) {
                        visitado[v] = true;
                        try fila.append(@intCast(v));
                    }
                }
            }

            return try ordem.toOwnedSlice();
        }

        /// DFS — Busca em profundidade (recursiva via pilha).
        pub fn dfs(self: *const Self, inicio: u32, allocator: Allocator) ![]u32 {
            var visitado = try allocator.alloc(bool, self.num_vertices);
            defer allocator.free(visitado);
            @memset(visitado, false);

            var pilha = std.ArrayList(u32).init(allocator);
            defer pilha.deinit();
            var ordem = std.ArrayList(u32).init(allocator);

            try pilha.append(inicio);

            while (pilha.items.len > 0) {
                const atual = pilha.pop();
                if (visitado[atual]) continue;
                visitado[atual] = true;
                try ordem.append(atual);

                var v: u32 = self.num_vertices;
                while (v > 0) {
                    v -= 1;
                    if (self.matriz[atual][v] == 1 and !visitado[v]) {
                        try pilha.append(v);
                    }
                }
            }

            return try ordem.toOwnedSlice();
        }

        /// Detecta ciclo usando DFS com cores.
        pub fn temCiclo(self: *const Self, allocator: Allocator) !bool {
            const Cor = enum { branco, cinza, preto };
            var cor = try allocator.alloc(Cor, self.num_vertices);
            defer allocator.free(cor);
            @memset(cor, .branco);

            for (0..self.num_vertices) |v| {
                if (cor[v] == .branco) {
                    if (try self.dfsCiclo(@intCast(v), cor, allocator)) return true;
                }
            }
            return false;
        }

        fn dfsCiclo(self: *const Self, v: u32, cor: []@import("std").meta.Tag(@TypeOf(cor[0])), allocator: Allocator) !bool {
            _ = allocator;
            cor[v] = .cinza;
            for (0..self.num_vertices) |u| {
                if (self.matriz[v][u] == 1) {
                    if (cor[u] == .cinza) return true;
                    if (cor[u] == .branco) {
                        if (try self.dfsCiclo(@intCast(u), cor, allocator)) return true;
                    }
                }
            }
            cor[v] = .preto;
            return false;
        }

        /// Imprime a matriz.
        pub fn imprimir(self: *const Self, writer: anytype) !void {
            try writer.writeAll("    ");
            for (0..self.num_vertices) |v| {
                try writer.print("{d:>3}", .{v});
            }
            try writer.writeAll("\n");
            for (0..self.num_vertices) |i| {
                try writer.print("{d:>3} ", .{i});
                for (0..self.num_vertices) |j| {
                    try writer.print("{d:>3}", .{self.matriz[i][j]});
                }
                try writer.writeAll("\n");
            }
        }
    };
}

pub fn main() !void {
    const stdout = std.io.getStdOut().writer();
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();

    // Grafo não-direcionado com 5 vértices
    var grafo = try GrafoMatriz(false).init(allocator, 5);
    defer grafo.deinit();

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

    try stdout.writeAll("=== Matriz de Adjacência ===\n");
    try grafo.imprimir(stdout);

    // Verificações
    try stdout.print("\nAresta 0-1: {}\n", .{grafo.temAresta(0, 1)});
    try stdout.print("Aresta 0-4: {}\n", .{grafo.temAresta(0, 4)});
    try stdout.print("Grau do vértice 1: {d}\n", .{grafo.grau(1)});

    // BFS e DFS
    const bfs_ordem = try grafo.bfs(0, allocator);
    defer allocator.free(bfs_ordem);
    try stdout.print("\nBFS a partir de 0: {any}\n", .{bfs_ordem});

    const dfs_ordem = try grafo.dfs(0, allocator);
    defer allocator.free(dfs_ordem);
    try stdout.print("DFS a partir de 0: {any}\n", .{dfs_ordem});

    // Grafo direcionado
    try stdout.writeAll("\n=== Grafo Direcionado ===\n");
    var digrafo = try GrafoMatriz(true).init(allocator, 4);
    defer digrafo.deinit();

    digrafo.adicionarAresta(0, 1);
    digrafo.adicionarAresta(1, 2);
    digrafo.adicionarAresta(2, 3);
    digrafo.adicionarAresta(3, 1); // Cria ciclo

    try digrafo.imprimir(stdout);
}