--- title: "Ordenação Topológica em Zig: Algoritmo de Kahn e Detecção de Ciclos" url: "https://ziglang.com.br/algoritmos/ordenacao-topologica-kahn/" markdown_url: "https://ziglang.com.br/algoritmos/ordenacao-topologica-kahn.MD" description: "Implemente ordenação topológica em Zig com o algoritmo de Kahn, graus de entrada, fila, detecção de ciclos e testes para grafos direcionados acíclicos." date: "2026-08-24" author: "Zig Brasil" --- # Ordenação Topológica em Zig: Algoritmo de Kahn e Detecção de Ciclos Implemente ordenação topológica em Zig com o algoritmo de Kahn, graus de entrada, fila, detecção de ciclos e testes para grafos direcionados acíclicos. # Ordenação Topológica em Zig: Algoritmo de Kahn e Detecção de Ciclos A **ordenação topológica em Zig** organiza os vértices de um grafo direcionado para que toda dependência apareça antes do item que depende dela. O **algoritmo de Kahn** resolve o problema em **O(V + E)** usando graus de entrada e uma fila. Ele também detecta ciclos: se não conseguir processar todos os vértices, não existe uma ordem válida. Use esse algoritmo para ordenar etapas de build, disciplinas com pré-requisitos, jobs de CI, migrações de banco, módulos de software e tarefas de um pipeline. A condição obrigatória é que o grafo seja um **DAG** (*Directed Acyclic Graph* ou grafo direcionado acíclico). Se houver dependência circular, como `A → B → C → A`, nenhuma sequência consegue respeitar todas as relações. ## Resposta rápida | Pergunta | Resposta | |---|---| | Entrada | grafo direcionado | | Condição para existir solução | não haver ciclos | | Estrutura principal do algoritmo de Kahn | fila de vértices com grau de entrada zero | | Complexidade | O(V + E) | | Espaço auxiliar | O(V) | | Detecta ciclo? | sim, pela contagem de vértices processados | | A ordem é única? | nem sempre | | Alternativa | DFS com estados e pós-ordem | A ideia prática é simples: uma tarefa pode ser executada quando não possui dependências pendentes. Depois de executá-la, removemos conceitualmente suas arestas e verificamos quais tarefas foram liberadas. ## O que é uma ordenação topológica Considere este conjunto de etapas de um projeto: ```text compilar ──→ testar ──→ empacotar ──→ publicar └────────────────→ empacotar ``` Uma sequência válida é: ```text compilar, testar, empacotar, publicar ``` A ordem `testar, compilar, empacotar, publicar` é inválida porque `testar` depende de `compilar`. A ordenação não compara valores como um algoritmo de sorting tradicional; ela respeita uma **ordem parcial** definida pelas arestas. Se duas tarefas forem independentes, mais de uma resposta pode existir. Por exemplo: ```text lint ───────→ publicar compilar ───→ publicar ``` Tanto `lint, compilar, publicar` quanto `compilar, lint, publicar` são válidas. O algoritmo deve prometer uma ordem correta, não necessariamente uma sequência única. ## Como o algoritmo de Kahn funciona O **grau de entrada** de um vértice é a quantidade de arestas que chegam até ele. Se `A → B`, então essa aresta acrescenta um ao grau de entrada de `B`. O algoritmo executa estas etapas: 1. calcula o grau de entrada de cada vértice; 2. coloca na fila todos os vértices cujo grau é zero; 3. remove um vértice da fila e o adiciona ao resultado; 4. para cada vizinho, reduz seu grau de entrada; 5. quando o grau de um vizinho chega a zero, adiciona-o à fila; 6. repete até a fila ficar vazia; 7. verifica se todos os vértices foram processados. Em pseudocódigo: ```text para cada aresta origem → destino: grau_entrada[destino] += 1 para cada vértice: se grau_entrada[vértice] == 0: fila.adicionar(vértice) enquanto fila não vazia: atual = fila.remover() resultado.adicionar(atual) para cada vizinho de atual: grau_entrada[vizinho] -= 1 se grau_entrada[vizinho] == 0: fila.adicionar(vizinho) se resultado contém menos de V vértices: existe ciclo ``` A fila começa com tudo que já pode ser executado. Cada remoção libera, potencialmente, novas tarefas. ## Representando as dependências em Zig Usaremos uma lista de adjacência. A posição `i` contém os vértices que dependem diretamente de `i`: ```zig const adjacencia = [_][]const usize{ &.{ 2, 3 }, // 0 libera 2 e 3 &.{ 3 }, // 1 libera 3 &.{ 4 }, // 2 libera 4 &.{ 4 }, // 3 libera 4 &.{}, // 4 não libera outro vértice }; ``` Isso representa: ```text 0 → 2 → 4 0 → 3 → 4 1 → 3 ``` Os vértices `0` e `1` começam com grau de entrada zero. Portanto, uma ordem possível é `0, 1, 2, 3, 4`. Dependendo da política da fila, `1, 0, 3, 2, 4` também pode ser válida. O contrato da representação precisa ser claro. Neste artigo, `adjacencia[A]` lista os itens liberados por `A`. Se sua entrada diz “a tarefa A depende de B”, converta para a aresta `B → A`, e não `A → B`. ## Implementação completa em Zig A função abaixo retorna um slice alocado com a ordem. O chamador é responsável por liberá-lo. Vértices inválidos e ciclos são erros explícitos. ```zig const std = @import("std"); const Allocator = std.mem.Allocator; pub fn ordenarTopologicamente( allocator: Allocator, adjacencia: []const []const usize, ) ![]usize { const quantidade = adjacencia.len; const graus_entrada = try allocator.alloc(usize, quantidade); defer allocator.free(graus_entrada); @memset(graus_entrada, 0); for (adjacencia) |vizinhos| { for (vizinhos) |destino| { if (destino >= quantidade) return error.VerticeInvalido; graus_entrada[destino] += 1; } } const fila = try allocator.alloc(usize, quantidade); defer allocator.free(fila); const ordem = try allocator.alloc(usize, quantidade); errdefer allocator.free(ordem); var inicio: usize = 0; var fim: usize = 0; var processados: usize = 0; for (graus_entrada, 0..) |grau, vertice| { if (grau == 0) { fila[fim] = vertice; fim += 1; } } while (inicio < fim) { const atual = fila[inicio]; inicio += 1; ordem[processados] = atual; processados += 1; for (adjacencia[atual]) |vizinho| { graus_entrada[vizinho] -= 1; if (graus_entrada[vizinho] == 0) { fila[fim] = vizinho; fim += 1; } } } if (processados != quantidade) { allocator.free(ordem); return error.CicloDetectado; } return ordem; } ``` A fila recebe capacidade `V` porque cada vértice entra nela no máximo uma vez: seu grau de entrada só chega a zero uma vez. Como ocorre na implementação de [BFS em Zig](/algoritmos/bfs-busca-largura/), índices crescentes bastam; não precisamos de uma fila circular para uma execução finita com no máximo `V` inserções. O array `graus_entrada` é mutável porque representa o número de dependências ainda pendentes durante a simulação. A lista de adjacência original permanece intacta, permitindo que o chamador reutilize o grafo. ## Testando uma ordem válida Um teste não deveria comparar uma sequência exata quando várias respostas são aceitas. É melhor verificar a propriedade central: para cada aresta `origem → destino`, a posição da origem precisa ser menor que a posição do destino. ```zig fn validarOrdem( allocator: Allocator, adjacencia: []const []const usize, ordem: []const usize, ) !bool { if (ordem.len != adjacencia.len) return false; const posicoes = try allocator.alloc(usize, ordem.len); defer allocator.free(posicoes); const vistos = try allocator.alloc(bool, ordem.len); defer allocator.free(vistos); @memset(vistos, false); for (ordem, 0..) |vertice, posicao| { if (vertice >= ordem.len or vistos[vertice]) return false; vistos[vertice] = true; posicoes[vertice] = posicao; } for (adjacencia, 0..) |vizinhos, origem| { for (vizinhos) |destino| { if (destino >= ordem.len) return false; if (posicoes[origem] >= posicoes[destino]) return false; } } return true; } test "Kahn produz uma ordenação topológica válida" { const allocator = std.testing.allocator; const adjacencia = [_][]const usize{ &.{ 2, 3 }, &.{ 3 }, &.{ 4 }, &.{ 4 }, &.{}, }; const ordem = try ordenarTopologicamente(allocator, &adjacencia); defer allocator.free(ordem); try std.testing.expect( try validarOrdem(allocator, &adjacencia, ordem), ); } ``` Execute com: ```bash zig test ordenacao_topologica.zig ``` Esse estilo de teste continua correto se a implementação trocar a fila FIFO por uma heap, se a ordem das adjacências mudar ou se novos vértices independentes forem adicionados. ## Como detectar um ciclo Considere: ```text 0 → 1 → 2 ↑ ↓ └───────┘ ``` Todos os vértices têm grau de entrada um. A fila começa vazia, nenhum item é processado e `processados != quantidade`. O algoritmo retorna `error.CicloDetectado`. Teste o caso explicitamente: ```zig test "Kahn detecta ciclo" { const allocator = std.testing.allocator; const com_ciclo = [_][]const usize{ &.{1}, &.{2}, &.{0}, }; try std.testing.expectError( error.CicloDetectado, ordenarTopologicamente(allocator, &com_ciclo), ); } ``` Se uma parte do grafo for acíclica e outra contiver ciclo, Kahn processará a parte liberada e parará quando restarem apenas vértices bloqueados. Comparar a contagem ao total detecta ambos os cenários. Esse método confirma que existe um ciclo, mas não mostra seu caminho. Se você precisa responder “quais tarefas formam a dependência circular?”, use [DFS em Zig](/algoritmos/dfs-busca-profundidade/) com três estados — não visitado, em processamento e concluído — e guarde predecessores ao encontrar uma aresta para um vértice ainda em processamento. ## Como obter uma ordem determinística A fila simples preserva a ordem numérica em que os vértices de grau zero são descobertos. Isso é correto, mas pode não atender uma ferramenta que exige resultados reproduzíveis por nome ou prioridade. Para obter a menor chave disponível em cada etapa, substitua a fila por uma **min-heap**. O custo passa de O(V + E) para **O((V + E) log V)**, mas o resultado fica canônico segundo o comparador escolhido. Exemplos de políticas: - menor identificador numérico primeiro; - nome de tarefa em ordem alfabética; - prioridade operacional antes do nome; - caminho de arquivo normalizado; - número da migração antes da descrição. Não use a ordem acidental de um `HashMap` como contrato público. Se o resultado vai para um lockfile, cache de build ou artefato versionado, escolha e documente uma regra determinística. ## Como saber se a ordem é única Durante a execução, observe quantas opções estão disponíveis. Se em qualquer etapa houver dois ou mais vértices com grau de entrada zero, existem pelo menos duas escolhas possíveis naquele ponto e a ordenação não é única. Uma variação simples mantém um contador do tamanho lógico da fila antes de remover o próximo item. Porém, se você precisa provar unicidade sob uma política específica, tome cuidado: uma heap sempre escolhe um único mínimo, mas isso não significa que o DAG só possui uma ordem. Outra forma de verificar uma ordem produzida é confirmar que existe uma aresta entre cada par consecutivo. Em um DAG, se a ordem topológica tem `V - 1` relações obrigando cada próximo vértice, ela é única. Para uma API prática, registrar “houve múltiplas opções disponíveis” durante Kahn costuma ser a solução mais direta. ## Kahn ou DFS? Os dois métodos executam em O(V + E): | Critério | Kahn | DFS | |---|---|---| | ideia central | remover graus de entrada zero | adicionar na pós-ordem | | estrutura | fila e array de graus | pilha de chamadas ou pilha explícita | | detecção de ciclo | contagem final | aresta para estado em processamento | | listar tarefas disponíveis agora | natural | menos direto | | reconstruir caminho do ciclo | exige trabalho extra | natural com predecessores | | risco com recursão profunda | não | sim, se recursivo | | ordem lexicográfica | heap no lugar da fila | exige política adicional | Kahn combina especialmente bem com schedulers. A fila representa exatamente o conjunto de tarefas prontas. Em um executor paralelo, vários workers podem consumir itens liberados, desde que a atualização dos graus seja sincronizada e cada tarefa seja publicada uma única vez. DFS é uma boa escolha quando você já percorre o grafo dessa forma ou precisa retornar o ciclo detalhado. Veja também a comparação entre [BFS e DFS](/algoritmos/bfs-busca-largura/) para entender por que fila e pilha produzem ordens de exploração diferentes. ## Aplicações práticas ### Build systems Arquivos-fonte, bibliotecas e etapas de geração formam um DAG. Uma biblioteca só pode ser linkada depois que seus objetos estiverem prontos. Ferramentas de build também usam a estrutura para encontrar tarefas independentes que podem rodar em paralelo. ### Pipelines de dados e CI Um job de deploy pode depender de build, testes e análise de segurança. Kahn permite descobrir o que está pronto agora e rejeitar uma configuração com dependência circular antes de iniciar o pipeline. ### Migrações de banco Quando migrações ou módulos declaram dependências explícitas, a ordenação define a sequência de aplicação. Para migrações numeradas linearmente, ordenar pelo número é mais simples; use um DAG quando houver ramificações reais. ### Planos de estudo Disciplinas e cursos possuem pré-requisitos. A ordenação gera uma sequência possível, mas ainda pode precisar considerar semestre, carga horária e oferta. O DAG resolve precedência, não todas as restrições do problema. ### Inicialização de serviços Componentes internos podem depender de configuração, conexão, cache e descoberta. Uma ordem topológica ajuda a inicializar e, invertida, a desligar componentes. Ainda assim, dependências de runtime devem ter timeouts e falhas explícitas; ordenar não garante disponibilidade. ## Erros comuns ### Inverter a direção da aresta Se `API depende de banco`, a aresta para ordenação é `banco → API`. Pergunte: “quando este vértice termina, qual outro ele libera?” ### Aceitar grafo não direcionado Uma aresta não direcionada adicionada nos dois sentidos forma um ciclo de comprimento dois. Ordenação topológica representa precedência assimétrica. ### Esquecer vértices isolados Um vértice sem arestas tem grau zero e precisa aparecer no resultado. Não derive o conjunto de vértices apenas das arestas; mantenha o total explicitamente. ### Retornar resultado parcial como sucesso Se a fila esvaziar antes de processar `V`, o prefixo produzido não é uma ordenação do grafo inteiro. Retorne erro ou um resultado que marque claramente o ciclo. ### Comparar teste com uma única sequência Quando há escolhas independentes, várias ordens são válidas. Valide todas as arestas ou imponha uma política determinística no contrato. ### Mutar o grafo original Remover arestas fisicamente é desnecessário e dificulta reutilização. Mantenha um array separado de graus restantes. ### Ignorar entradas duplicadas Duas arestas idênticas aumentam o grau duas vezes e também serão reduzidas duas vezes, portanto o algoritmo ainda pode terminar. Porém, duplicatas normalmente indicam dado ruim e desperdiçam memória. Decida se a ingestão deve deduplicar ou rejeitar. ## Checklist para produção - defina claramente o sentido de cada aresta; - valide todos os índices antes de acessar arrays; - inclua vértices isolados; - diferencie grafo vazio de entrada inválida; - retorne erro se nem todos os vértices forem processados; - escolha fila para O(V + E) ou heap para ordem canônica; - não exponha a ordem acidental de mapas hash; - valide propriedades, não apenas uma sequência fixa; - limite tamanho e quantidade de arestas vindas de input externo; - deduplique dependências se o domínio não aceita repetições; - use DFS se precisar reconstruir o caminho do ciclo; - monitore duração e tamanho do grafo em schedulers críticos. ## Conclusão A ordenação topológica transforma dependências de um DAG em uma sequência executável. Em Zig, o algoritmo de Kahn pode ser implementado com três estruturas simples: um array de graus de entrada, uma fila e um resultado. Cada vértice entra na fila uma vez e cada aresta é examinada uma vez, mantendo o custo em **O(V + E)**. A regra de operação é direta: processe tudo que não tem dependência pendente e libere seus vizinhos. Se o processo parar antes de consumir todos os vértices, há um ciclo e nenhuma ordem completa existe. Para continuar estudando grafos, veja [BFS em Zig](/algoritmos/bfs-busca-largura/) para percursos por níveis, [DFS em Zig](/algoritmos/dfs-busca-profundidade/) para exploração e reconstrução de ciclos, e [Dijkstra em Zig](/algoritmos/dijkstra/) para caminhos mínimos com pesos não negativos.