--- title: "Grafo com Matriz de Adjacência em Zig — Implementação Completa" url: "https://ziglang.com.br/estruturas-dados/grafo-com-matriz-de-adjac%C3%AAncia-em-zig-implementa%C3%A7%C3%A3o-completa/" markdown_url: "https://ziglang.com.br/estruturas-dados/grafo-com-matriz-de-adjac%C3%AAncia-em-zig-implementa%C3%A7%C3%A3o-completa.MD" description: "Aprenda Grafo com matriz de adjacência em Zig. Verificação de adjacência O(1), BFS, DFS e detecção de ciclos com código funcional." date: "2026-02-21" author: "Zig Brasil" --- # Grafo com Matriz de Adjacência em Zig — Implementação Completa Aprenda Grafo com matriz de adjacência em Zig. Verificação de adjacência O(1), BFS, DFS e detecção de ciclos com código funcional. # Grafo com Matriz de Adjacência em Zig — Implementação Completa A representação por **matriz de adjacência** usa uma matriz V x V onde `matriz[i][j] = 1` indica que existe aresta de `i` para `j`. Esta representação permite verificar adjacência em O(1), sendo ideal para grafos densos (muitas arestas) ou quando a verificação de adjacência é frequente. ## Conceito ``` 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) ``` ## Implementação em Zig ```zig 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); } ``` ## Comparação: Lista vs. Matriz | Operação | Lista de Adjacência | Matriz de Adjacência | |----------|--------------------|--------------------| | **Espaço** | O(V + E) | O(V^2) | | **Adicionar aresta** | O(1) | O(1) | | **Verificar adjacência** | O(grau) | **O(1)** | | **Iterar vizinhos** | O(grau) | O(V) | | **Remover aresta** | O(grau) | **O(1)** | Use **matriz** quando: grafo denso (E perto de V^2), verificação frequente de adjacência, V pequeno. Use **lista** quando: grafo esparso, iteração frequente sobre vizinhos, V grande. ## Recursos Relacionados - [Grafo com Lista de Adjacência](/estruturas-dados/grafo-lista-adjacencia/) — Representação para grafos esparsos - [Grafo Ponderado](/estruturas-dados/grafo-ponderado/) — Grafo com pesos nas arestas - [Union-Find](/estruturas-dados/union-find/) — Componentes conexas - [Perguntas de Entrevista: Algoritmos](/entrevistas/perguntas-algoritmos-zig/)