Grafo com Lista de Adjacência em Zig — Implementação Completa
Um grafo é uma estrutura composta por vértices (nós) e arestas (conexões entre nós). A representação por lista de adjacência armazena, para cada vértice, a lista dos vértices vizinhos. Esta representação é eficiente em espaço para grafos esparsos (poucos arestas relativo ao número de vértices) e permite iteração rápida sobre os vizinhos.
Conceito
Grafo não-direcionado com 6 vértices:
0 --- 1 --- 2
| | |
3 --- 4 5
Lista de Adjacência:
0 → [1, 3]
1 → [0, 2, 4]
2 → [1, 5]
3 → [0, 4]
4 → [1, 3]
5 → [2]
Espaço: O(V + E) onde V = vértices, E = arestas
Implementação em Zig
const std = @import("std");
const Allocator = std.mem.Allocator;
/// Grafo com lista de adjacência usando ArrayLists.
pub fn Grafo(comptime direcionado: bool) type {
return struct {
const Self = @This();
adjacencias: []std.ArrayList(u32),
num_vertices: u32,
num_arestas: u32,
allocator: Allocator,
pub fn init(allocator: Allocator, num_vertices: u32) !Self {
const adj = try allocator.alloc(std.ArrayList(u32), num_vertices);
for (adj) |*lista| {
lista.* = std.ArrayList(u32).init(allocator);
}
return .{
.adjacencias = adj,
.num_vertices = num_vertices,
.num_arestas = 0,
.allocator = allocator,
};
}
pub fn deinit(self: *Self) void {
for (self.adjacencias) |*lista| {
lista.deinit();
}
self.allocator.free(self.adjacencias);
}
/// Adiciona aresta entre u e v.
pub fn adicionarAresta(self: *Self, u: u32, v: u32) !void {
try self.adjacencias[u].append(v);
if (!direcionado) {
try self.adjacencias[v].append(u);
}
self.num_arestas += 1;
}
/// Retorna vizinhos de um vértice.
pub fn vizinhos(self: *const Self, v: u32) []const u32 {
return self.adjacencias[v].items;
}
/// Grau de um vértice.
pub fn grau(self: *const Self, v: u32) usize {
return self.adjacencias[v].items.len;
}
/// BFS — Busca em largura a partir de um vértice.
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 (self.vizinhos(atual)) |vizinho| {
if (!visitado[vizinho]) {
visitado[vizinho] = true;
try fila.append(vizinho);
}
}
}
return try ordem.toOwnedSlice();
}
/// DFS — Busca em profundidade a partir de um vértice.
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);
// Itera em ordem reversa para manter a ordem natural
const viz = self.vizinhos(atual);
var i: usize = viz.len;
while (i > 0) {
i -= 1;
if (!visitado[viz[i]]) {
try pilha.append(viz[i]);
}
}
}
return try ordem.toOwnedSlice();
}
/// Encontra componentes conexas (grafo não-direcionado).
pub fn componentesConexas(self: *const Self, allocator: Allocator) ![][]u32 {
var visitado = try allocator.alloc(bool, self.num_vertices);
defer allocator.free(visitado);
@memset(visitado, false);
var componentes = std.ArrayList([]u32).init(allocator);
for (0..self.num_vertices) |v| {
if (!visitado[@intCast(v)]) {
const comp = try self.bfsComponente(@intCast(v), visitado, allocator);
try componentes.append(comp);
}
}
return try componentes.toOwnedSlice();
}
fn bfsComponente(self: *const Self, inicio: u32, visitado: []bool, allocator: Allocator) ![]u32 {
var fila = std.ArrayList(u32).init(allocator);
defer fila.deinit();
var comp = std.ArrayList(u32).init(allocator);
visitado[inicio] = true;
try fila.append(inicio);
while (fila.items.len > 0) {
const atual = fila.orderedRemove(0);
try comp.append(atual);
for (self.vizinhos(atual)) |viz| {
if (!visitado[viz]) {
visitado[viz] = true;
try fila.append(viz);
}
}
}
return try comp.toOwnedSlice();
}
};
}
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 6 vértices
var grafo = try Grafo(false).init(allocator, 6);
defer grafo.deinit();
try grafo.adicionarAresta(0, 1);
try grafo.adicionarAresta(0, 3);
try grafo.adicionarAresta(1, 2);
try grafo.adicionarAresta(1, 4);
try grafo.adicionarAresta(2, 5);
try grafo.adicionarAresta(3, 4);
// Vizinhos
try stdout.writeAll("=== Lista de Adjacência ===\n");
for (0..grafo.num_vertices) |v| {
try stdout.print(" {d} → {any}\n", .{ v, grafo.vizinhos(@intCast(v)) });
}
// BFS
const ordem_bfs = try grafo.bfs(0, allocator);
defer allocator.free(ordem_bfs);
try stdout.print("\nBFS a partir de 0: {any}\n", .{ordem_bfs});
// DFS
const ordem_dfs = try grafo.dfs(0, allocator);
defer allocator.free(ordem_dfs);
try stdout.print("DFS a partir de 0: {any}\n", .{ordem_dfs});
// Componentes conexas
const comps = try grafo.componentesConexas(allocator);
defer {
for (comps) |c| allocator.free(c);
allocator.free(comps);
}
try stdout.print("\nComponentes conexas: {d}\n", .{comps.len});
for (comps, 0..) |c, i| {
try stdout.print(" Componente {d}: {any}\n", .{ i, c });
}
}
Análise de Complexidade
| Operação | Tempo | Espaço |
|---|---|---|
| Adicionar aresta | O(1) | O(1) |
| Verificar adjacência | O(grau(v)) | O(1) |
| Iterar vizinhos | O(grau(v)) | O(1) |
| BFS / DFS | O(V + E) | O(V) |
| Espaço total | — | O(V + E) |
Recursos Relacionados
- Grafo com Matriz de Adjacência — Representação com matriz
- Grafo Ponderado — Grafo com pesos nas arestas
- Union-Find — Componentes conexas eficiente
- Perguntas de Entrevista: Algoritmos