--- title: "Ordenação Topológica em Zig — Implementação e Explicação" url: "https://ziglang.com.br/algoritmos/ordena%C3%A7%C3%A3o-topol%C3%B3gica-em-zig-implementa%C3%A7%C3%A3o-e-explica%C3%A7%C3%A3o/" markdown_url: "https://ziglang.com.br/algoritmos/ordena%C3%A7%C3%A3o-topol%C3%B3gica-em-zig-implementa%C3%A7%C3%A3o-e-explica%C3%A7%C3%A3o.MD" description: "Aprenda Ordenação Topológica implementada em Zig. Ordenação de grafos acíclicos dirigidos (DAG) com algoritmo de Kahn e DFS, código e análise." date: "2026-02-21" author: "Zig Brasil" --- # Ordenação Topológica em Zig — Implementação e Explicação Aprenda Ordenação Topológica implementada em Zig. Ordenação de grafos acíclicos dirigidos (DAG) com algoritmo de Kahn e DFS, código e análise. # Ordenação Topológica em Zig — Implementação e Explicação A **Ordenação Topológica** ordena os vértices de um **grafo acíclico dirigido (DAG)** de forma que, para cada aresta u → v, u aparece antes de v na ordenação. É fundamental para resolver problemas de dependências. ## Como Funciona ### Algoritmo de Kahn (BFS) 1. Calcule o grau de entrada de cada vértice 2. Adicione todos os vértices com grau de entrada 0 a uma fila 3. Enquanto a fila não estiver vazia: - Remova um vértice, adicione-o ao resultado - Reduza o grau de entrada dos vizinhos - Se algum vizinho ficou com grau 0, adicione-o à fila ### Visualização ``` DAG de dependências: 5 → 0 4 → 0 4 → 1 2 → 3 3 → 1 5 → 2 5 ----→ 0 ←---- 4 | | ↓ ↓ 2 ---→ 3 ---→ 1 Grau de entrada: [2, 2, 1, 1, 0, 0] Vértices com grau 0: {4, 5} Passo 1: remove 4 → grau de [0,1] diminui → 0:[1], 1:[1] Passo 2: remove 5 → grau de [0,2] diminui → 0:[0], 2:[0] Passo 3: remove 0 (grau 0 agora) Passo 4: remove 2 → 3:[0] Passo 5: remove 3 → 1:[0] Passo 6: remove 1 Resultado: [4, 5, 0, 2, 3, 1] ou [5, 4, 2, 0, 3, 1] ... (Pode haver múltiplas ordenações válidas) ``` ## Implementação em Zig ```zig const std = @import("std"); const Allocator = std.mem.Allocator; const GrafoDirecionado = struct { adjacencia: []std.ArrayList(u32), num_vertices: u32, allocator: Allocator, pub fn init(allocator: Allocator, n: u32) !GrafoDirecionado { const adj = try allocator.alloc(std.ArrayList(u32), n); for (adj) |*lista| lista.* = std.ArrayList(u32).init(allocator); return .{ .adjacencia = adj, .num_vertices = n, .allocator = allocator }; } pub fn deinit(self: *GrafoDirecionado) void { for (self.adjacencia) |*l| l.deinit(); self.allocator.free(self.adjacencia); } pub fn addAresta(self: *GrafoDirecionado, de: u32, para: u32) !void { try self.adjacencia[de].append(para); } }; /// Ordenação Topológica usando o algoritmo de Kahn (BFS). /// Retorna null se o grafo contiver ciclo. pub fn kahnTopologicalSort( allocator: Allocator, grafo: *const GrafoDirecionado, ) !?[]u32 { const n = grafo.num_vertices; // Calcula grau de entrada const grau_entrada = try allocator.alloc(u32, n); defer allocator.free(grau_entrada); @memset(grau_entrada, 0); for (grafo.adjacencia) |lista| { for (lista.items) |v| { grau_entrada[v] += 1; } } // Fila com vértices de grau de entrada 0 var fila = std.ArrayList(u32).init(allocator); defer fila.deinit(); var i: u32 = 0; while (i < n) : (i += 1) { if (grau_entrada[i] == 0) try fila.append(i); } var resultado = std.ArrayList(u32).init(allocator); while (fila.items.len > 0) { const v = fila.orderedRemove(0); try resultado.append(v); for (grafo.adjacencia[v].items) |vizinho| { grau_entrada[vizinho] -= 1; if (grau_entrada[vizinho] == 0) { try fila.append(vizinho); } } } // Se não processou todos os vértices, há ciclo if (resultado.items.len != n) { resultado.deinit(); return null; } return try resultado.toOwnedSlice(); } /// Ordenação Topológica usando DFS. pub fn dfsTopologicalSort( allocator: Allocator, grafo: *const GrafoDirecionado, ) !?[]u32 { const n = grafo.num_vertices; // 0=branco, 1=cinza, 2=preto const cor = try allocator.alloc(u8, n); defer allocator.free(cor); @memset(cor, 0); var pilha = std.ArrayList(u32).init(allocator); var tem_ciclo = false; var v: u32 = 0; while (v < n) : (v += 1) { if (cor[v] == 0) { dfsTopoHelper(grafo, v, cor, &pilha, &tem_ciclo) catch {}; } } if (tem_ciclo) { pilha.deinit(); return null; } // Inverte a pilha para obter a ordenação const resultado = try pilha.toOwnedSlice(); std.mem.reverse(u32, resultado); return resultado; } fn dfsTopoHelper( grafo: *const GrafoDirecionado, v: u32, cor: []u8, pilha: *std.ArrayList(u32), tem_ciclo: *bool, ) !void { cor[v] = 1; // cinza for (grafo.adjacencia[v].items) |vizinho| { if (cor[vizinho] == 1) { tem_ciclo.* = true; return; } if (cor[vizinho] == 0) { try dfsTopoHelper(grafo, vizinho, cor, pilha, tem_ciclo); } } cor[v] = 2; // preto try pilha.append(v); } 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 GrafoDirecionado.init(allocator, 6); defer grafo.deinit(); try grafo.addAresta(5, 0); try grafo.addAresta(5, 2); try grafo.addAresta(4, 0); try grafo.addAresta(4, 1); try grafo.addAresta(2, 3); try grafo.addAresta(3, 1); // Kahn if (try kahnTopologicalSort(allocator, &grafo)) |ordem| { defer allocator.free(ordem); try stdout.print("Kahn: ", .{}); for (ordem) |v| try stdout.print("{d} ", .{v}); try stdout.print("\n", .{}); } else { try stdout.print("Ciclo detectado!\n", .{}); } // DFS if (try dfsTopologicalSort(allocator, &grafo)) |ordem| { defer allocator.free(ordem); try stdout.print("DFS: ", .{}); for (ordem) |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) | ## Aplicações - **Resolução de dependências**: compilação, instalação de pacotes - **Agendamento de tarefas**: ordem de execução com pré-requisitos - **Avaliação de expressões**: ordem de cálculo - **Curricula universitários**: pré-requisitos de disciplinas ## Recursos Relacionados - [DFS em Zig](/algoritmos/dfs-busca-profundidade/) — Base do método DFS - [BFS em Zig](/algoritmos/bfs-busca-largura/) — Base do algoritmo de Kahn - [Grafo — Lista de Adjacência](/estruturas-dados/grafo-lista-adjacencia/) — Representação usada - [Fila](/estruturas-dados/fila/) — Estrutura usada no Kahn