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

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:

compilar ──→ testar ──→ empacotar ──→ publicar
    └────────────────→ empacotar

Uma sequência válida é:

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:

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:

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:

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:

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.

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, í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.

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:

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:

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:

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 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):

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 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 para percursos por níveis, DFS em Zig para exploração e reconstrução de ciclos, e Dijkstra em Zig para caminhos mínimos com pesos não negativos.