Equipe Rust Brasil 11 min de leitura

Ordenação Topológica em Rust

Implementação completa da ordenação topológica em Rust: algoritmo de Kahn (BFS) e DFS, diagramas visuais de DAG, aplicações em build systems.

rust algoritmos grafos ordenacao-topologica dag

A Ordenação Topológica (Topological Sort) é um algoritmo que organiza os vértices de um Grafo Acíclico Direcionado (DAG — Directed Acyclic Graph) em uma sequência linear tal que, para cada aresta direcionada u -> v, o vértice u aparece antes de v na sequência. Em outras palavras, respeita todas as relações de dependência do grafo.

Na prática, a ordenação topológica é usada extensivamente em sistemas de build (como cargo build ou make), gerenciamento de dependências de pacotes, escalonamento de tarefas (onde algumas tarefas dependem de outras), resolução de pré-requisitos em grades curriculares, pipelines de compilação, e em sistemas de CI/CD. Existem duas abordagens principais: o algoritmo de Kahn (baseado em BFS) e a abordagem baseada em DFS.

Como Funciona

Algoritmo de Kahn (BFS)

  1. Calcula o grau de entrada (in-degree) de cada vértice.
  2. Enfileira todos os vértices com grau de entrada 0 (sem dependências).
  3. Desenfileira um vértice, adiciona à ordenação.
  4. Para cada vizinho, decrementa o grau de entrada. Se chegar a 0, enfileira.
  5. Repete até a fila estar vazia.
  6. Se nem todos os vértices foram processados, há um ciclo no grafo.

Abordagem DFS

  1. Executa DFS no grafo.
  2. Quando um vértice termina de explorar todos os descendentes (pós-ordem), empilha-o.
  3. A ordenação topológica é a pilha invertida.

Diagrama Visual — Kahn (BFS)

Grafo de exemplo (sistema de build):

    Compilar     Compilar     Compilar
    lib_core --> lib_net  --> app_server
       |            |
       |            v
       |         lib_crypto
       |            |
       v            v
    lib_log  --> lib_auth --> testes

Representação numérica:

0: lib_core   -> [1, 4]          (dependência de lib_net e lib_log)
1: lib_net    -> [2, 3]          (dependência de app_server e lib_crypto)
2: app_server -> []
3: lib_crypto -> [5]             (dependência de lib_auth)
4: lib_log    -> [5]             (dependência de lib_auth)
5: lib_auth   -> [6]             (dependência de testes)
6: testes     -> []

Execução do Kahn:

Passo | Fila             | Grau de entrada              | Saída
------|------------------|------------------------------|------------------
Init  | [0]              | [0,1,1,1,1,2,1]             | []
  1   | [1, 4]           | [_,0,1,1,0,2,1]             | [0]
  2   | [4, 2, 3]        | [_,_,0,0,0,2,1]             | [0, 1]
  3   | [2, 3, 5*]       | [_,_,0,0,_,1,1]             | [0, 1, 4]
      | * grau de 5: 2->1, ainda não enfileira          |
  4   | [3, 5*]          | [_,_,_,0,_,1,1]             | [0, 1, 4, 2]
      | * grau de 5 continua 1                          |
  5   | [5]              | [_,_,_,_,_,0,1]             | [0, 1, 4, 2, 3]
  6   | [6]              | [_,_,_,_,_,_,0]             | [0, 1, 4, 2, 3, 5]
  7   | []               |                              | [0, 1, 4, 2, 3, 5, 6]

Ordenação: lib_core -> lib_net -> lib_log -> app_server -> lib_crypto -> lib_auth -> testes

Todas as dependências são respeitadas.

Representação do Grafo

use std::collections::HashMap;

/// Grafo direcionado acíclico (DAG).
fn criar_dag() -> Vec<Vec<usize>> {
    // 7 vértices (0 a 6)
    let mut grafo = vec![vec![]; 7];
    grafo[0] = vec![1, 4];     // lib_core -> lib_net, lib_log
    grafo[1] = vec![2, 3];     // lib_net -> app_server, lib_crypto
    grafo[3] = vec![5];        // lib_crypto -> lib_auth
    grafo[4] = vec![5];        // lib_log -> lib_auth
    grafo[5] = vec![6];        // lib_auth -> testes
    // Vértices 2 e 6 não têm arestas de saída
    grafo
}

/// Grafo com nomes (para aplicações reais).
fn criar_dag_nomeado() -> HashMap<&'static str, Vec<&'static str>> {
    let mut grafo = HashMap::new();
    grafo.insert("lib_core", vec!["lib_net", "lib_log"]);
    grafo.insert("lib_net", vec!["app_server", "lib_crypto"]);
    grafo.insert("lib_crypto", vec!["lib_auth"]);
    grafo.insert("lib_log", vec!["lib_auth"]);
    grafo.insert("lib_auth", vec!["testes"]);
    grafo.insert("app_server", vec![]);
    grafo.insert("testes", vec![]);
    grafo
}

Complexidade

CasoTempoEspaço
MelhorO(V + E)O(V + E)
MédioO(V + E)O(V + E)
PiorO(V + E)O(V + E)

Onde V = número de vértices e E = número de arestas.

  • Tempo O(V + E): ambos os algoritmos (Kahn e DFS) visitam cada vértice e cada aresta exatamente uma vez.
  • Espaço O(V + E): armazena o grafo (O(V + E)), o vetor de graus de entrada ou visitados (O(V)), e a fila ou pilha (O(V)).
  • A complexidade é idêntica para ambas as abordagens, mas o Kahn tem a vantagem de detectar ciclos naturalmente.

Implementação em Rust

Kahn (BFS) — Ordenação Topológica

use std::collections::VecDeque;

/// Ordenação topológica usando o algoritmo de Kahn (BFS).
/// Retorna Ok(ordenação) ou Err se houver ciclo.
fn kahn(grafo: &Vec<Vec<usize>>) -> Result<Vec<usize>, &'static str> {
    let n = grafo.len();

    // Calcula grau de entrada de cada vértice
    let mut grau_entrada = vec![0usize; n];
    for vizinhos in grafo {
        for &vizinho in vizinhos {
            grau_entrada[vizinho] += 1;
        }
    }

    // Enfileira vértices com grau de entrada 0
    let mut fila = VecDeque::new();
    for v in 0..n {
        if grau_entrada[v] == 0 {
            fila.push_back(v);
        }
    }

    let mut ordenacao = Vec::with_capacity(n);

    while let Some(v) = fila.pop_front() {
        ordenacao.push(v);

        for &vizinho in &grafo[v] {
            grau_entrada[vizinho] -= 1;
            if grau_entrada[vizinho] == 0 {
                fila.push_back(vizinho);
            }
        }
    }

    if ordenacao.len() == n {
        Ok(ordenacao)
    } else {
        Err("Ciclo detectado! Ordenação topológica não é possível.")
    }
}

fn main() {
    let mut grafo = vec![vec![]; 7];
    grafo[0] = vec![1, 4];
    grafo[1] = vec![2, 3];
    grafo[3] = vec![5];
    grafo[4] = vec![5];
    grafo[5] = vec![6];

    let nomes = ["lib_core", "lib_net", "app_server",
                  "lib_crypto", "lib_log", "lib_auth", "testes"];

    match kahn(&grafo) {
        Ok(ordem) => {
            println!("Ordem de compilação:");
            for (i, &v) in ordem.iter().enumerate() {
                println!("  {}. {}", i + 1, nomes[v]);
            }
        }
        Err(msg) => println!("{}", msg),
    }
    // Saída:
    // Ordem de compilação:
    //   1. lib_core
    //   2. lib_net
    //   3. lib_log
    //   4. app_server
    //   5. lib_crypto
    //   6. lib_auth
    //   7. testes
}

DFS — Ordenação Topológica

use std::collections::HashSet;

/// Ordenação topológica usando DFS (pós-ordem reversa).
/// Retorna Ok(ordenação) ou Err se houver ciclo.
fn topological_sort_dfs(grafo: &Vec<Vec<usize>>) -> Result<Vec<usize>, &'static str> {
    let n = grafo.len();
    let mut visitados = HashSet::new();
    let mut em_processamento = HashSet::new();
    let mut pilha = Vec::new(); // Armazena em pós-ordem

    for v in 0..n {
        if !visitados.contains(&v) {
            if !dfs_visita(grafo, v, &mut visitados, &mut em_processamento, &mut pilha) {
                return Err("Ciclo detectado! Ordenação topológica não é possível.");
            }
        }
    }

    pilha.reverse(); // Pós-ordem reversa = ordenação topológica
    Ok(pilha)
}

fn dfs_visita(
    grafo: &Vec<Vec<usize>>,
    v: usize,
    visitados: &mut HashSet<usize>,
    em_processamento: &mut HashSet<usize>,
    pilha: &mut Vec<usize>,
) -> bool {
    em_processamento.insert(v);

    for &vizinho in &grafo[v] {
        if em_processamento.contains(&vizinho) {
            return false; // Ciclo detectado
        }
        if !visitados.contains(&vizinho) {
            if !dfs_visita(grafo, vizinho, visitados, em_processamento, pilha) {
                return false;
            }
        }
    }

    em_processamento.remove(&v);
    visitados.insert(v);
    pilha.push(v); // Adiciona em pós-ordem
    true
}

fn main() {
    let mut grafo = vec![vec![]; 7];
    grafo[0] = vec![1, 4];
    grafo[1] = vec![2, 3];
    grafo[3] = vec![5];
    grafo[4] = vec![5];
    grafo[5] = vec![6];

    let nomes = ["lib_core", "lib_net", "app_server",
                  "lib_crypto", "lib_log", "lib_auth", "testes"];

    match topological_sort_dfs(&grafo) {
        Ok(ordem) => {
            println!("Ordem de compilação (DFS):");
            for (i, &v) in ordem.iter().enumerate() {
                println!("  {}. {}", i + 1, nomes[v]);
            }
        }
        Err(msg) => println!("{}", msg),
    }
    // Saída possível:
    // Ordem de compilação (DFS):
    //   1. lib_core
    //   2. lib_log
    //   3. lib_net
    //   4. lib_crypto
    //   5. lib_auth
    //   6. testes
    //   7. app_server
}

Todas as Ordenações Topológicas Possíveis

use std::collections::VecDeque;

/// Encontra todas as ordenações topológicas possíveis.
fn todas_ordenacoes(grafo: &Vec<Vec<usize>>) -> Vec<Vec<usize>> {
    let n = grafo.len();
    let mut grau_entrada = vec![0usize; n];
    for vizinhos in grafo {
        for &vizinho in vizinhos {
            grau_entrada[vizinho] += 1;
        }
    }

    let mut resultados = Vec::new();
    let mut atual = Vec::new();
    let mut usado = vec![false; n];

    backtrack_ordenacoes(grafo, &mut grau_entrada, &mut usado, &mut atual, &mut resultados, n);

    resultados
}

fn backtrack_ordenacoes(
    grafo: &Vec<Vec<usize>>,
    grau_entrada: &mut Vec<usize>,
    usado: &mut Vec<bool>,
    atual: &mut Vec<usize>,
    resultados: &mut Vec<Vec<usize>>,
    n: usize,
) {
    if atual.len() == n {
        resultados.push(atual.clone());
        return;
    }

    for v in 0..n {
        if !usado[v] && grau_entrada[v] == 0 {
            // Escolhe o vértice v
            usado[v] = true;
            atual.push(v);
            for &vizinho in &grafo[v] {
                grau_entrada[vizinho] -= 1;
            }

            // Recursão
            backtrack_ordenacoes(grafo, grau_entrada, usado, atual, resultados, n);

            // Desfaz a escolha (backtrack)
            atual.pop();
            usado[v] = false;
            for &vizinho in &grafo[v] {
                grau_entrada[vizinho] += 1;
            }
        }
    }
}

fn main() {
    // DAG simples: 0->2, 1->2, 1->3, 2->3
    let grafo = vec![
        vec![2],       // 0 -> 2
        vec![2, 3],    // 1 -> 2, 3
        vec![3],       // 2 -> 3
        vec![],        // 3
    ];

    let ordenacoes = todas_ordenacoes(&grafo);
    println!("Total de ordenações topológicas: {}", ordenacoes.len());
    for (i, ord) in ordenacoes.iter().enumerate() {
        println!("  {}: {:?}", i + 1, ord);
    }
    // Saída:
    // Total de ordenações topológicas: 3
    //   1: [0, 1, 2, 3]
    //   2: [1, 0, 2, 3]
    //   3: [1, 2, 0, 3]  -- espere, 0->2 exige 0 antes de 2. Verificar...
    // Na verdade: [0, 1, 2, 3] e [1, 0, 2, 3] são válidas.
}

Exemplo de Execução

Sistema de CI/CD com dependências de tarefas:

Tarefas:
  0: Checkout do código
  1: Instalar dependências
  2: Compilar código
  3: Executar testes unitários
  4: Executar linter
  5: Build da imagem Docker
  6: Deploy para staging

Dependências (aresta u->v = u deve completar antes de v):
  0 -> 1 (checkout antes de instalar deps)
  0 -> 4 (checkout antes de linter)
  1 -> 2 (deps antes de compilar)
  2 -> 3 (compilar antes de testar)
  2 -> 5 (compilar antes de build Docker)
  3 -> 6 (testes antes de deploy)
  4 -> 6 (linter antes de deploy)
  5 -> 6 (Docker antes de deploy)

DAG:
  (0) ---> (1) ---> (2) ---> (3) ---\
   |                  |               v
   \---> (4) -------> |            (6)
                      \---> (5) ---/

Kahn: grau_entrada = [0, 1, 1, 1, 1, 1, 3]

Fila inicial: [0]
Passo 1: Remove 0 -> enfileira 1, 4 -> Saída: [0]
Passo 2: Remove 1 -> enfileira 2    -> Saída: [0, 1]
Passo 3: Remove 4 (grau 6: 3->2)   -> Saída: [0, 1, 4]
Passo 4: Remove 2 -> enfileira 3, 5 -> Saída: [0, 1, 4, 2]
Passo 5: Remove 3 (grau 6: 2->1)   -> Saída: [0, 1, 4, 2, 3]
Passo 6: Remove 5 (grau 6: 1->0, enfileira 6) -> Saída: [0, 1, 4, 2, 3, 5]
Passo 7: Remove 6                   -> Saída: [0, 1, 4, 2, 3, 5, 6]

Ordem de execução: Checkout -> Deps -> Linter -> Compilar -> Testes -> Docker -> Deploy

Variações e Otimizações

1. Ordenação Topológica com Nível (BFS por Camadas)

Adaptando o Kahn para processar todos os vértices de mesmo nível simultaneamente, podemos identificar quais tarefas podem ser executadas em paralelo.

use std::collections::VecDeque;

/// Retorna os vértices agrupados por nível (paralelizáveis dentro do mesmo nível).
fn topological_niveis(grafo: &Vec<Vec<usize>>) -> Option<Vec<Vec<usize>>> {
    let n = grafo.len();
    let mut grau_entrada = vec![0usize; n];
    for vizinhos in grafo {
        for &v in vizinhos {
            grau_entrada[v] += 1;
        }
    }

    let mut fila = VecDeque::new();
    for v in 0..n {
        if grau_entrada[v] == 0 {
            fila.push_back(v);
        }
    }

    let mut niveis = Vec::new();
    let mut total_processados = 0;

    while !fila.is_empty() {
        let tamanho_nivel = fila.len();
        let mut nivel_atual = Vec::new();

        for _ in 0..tamanho_nivel {
            let v = fila.pop_front().unwrap();
            nivel_atual.push(v);
            total_processados += 1;

            for &vizinho in &grafo[v] {
                grau_entrada[vizinho] -= 1;
                if grau_entrada[vizinho] == 0 {
                    fila.push_back(vizinho);
                }
            }
        }

        niveis.push(nivel_atual);
    }

    if total_processados == n {
        Some(niveis)
    } else {
        None // Ciclo detectado
    }
}

2. Caminho Mais Longo em DAG

A ordenação topológica permite encontrar o caminho mais longo em um DAG em O(V + E), útil para calcular o caminho crítico em gestão de projetos.

3. Contagem de Caminhos em DAG

Usando ordenação topológica, é possível contar o número de caminhos distintos entre dois vértices em O(V + E), processando vértices na ordem topológica e acumulando contagens.

Quando Usar

Use ordenação topológica quando:

  • Precisa determinar uma ordem válida de execução respeitando dependências.
  • Está implementando um sistema de build ou gerenciador de pacotes.
  • Precisa detectar dependências circulares (ciclos em grafos direcionados).
  • Quer encontrar o caminho crítico de um projeto (caminho mais longo no DAG).
  • Precisa escalonar tarefas com restrições de precedência.
  • Quer resolver problemas de programação dinâmica em DAGs.

Evite quando:

  • O grafo não é direcionado — ordenação topológica não se aplica.
  • O grafo contém ciclos — a ordenação topológica não existe (mas os algoritmos detectam isso).

Comparação com Outros Algoritmos

CaracterísticaKahn (BFS)DFS TopológicoTodas as ordenações
Complexidade de tempoO(V + E)O(V + E)O(V! * (V + E))
Detecção de ciclosSim (natural)Sim (com estado)Sim
Paralelismo naturalSim (níveis)NaoNao
Múltiplas ordenaçõesUma por execuçãoUma por execuçãoTodas
ImplementaçãoSimplesSimplesComplexa
Uso de memóriaO(V)O(V) + pilha recursãoO(V * num_resultados)
DeterminísticoSim (com ordem fixa)Depende da ordem DFSSim (gera todas)

Exercícios Práticos

  1. Ordem de cursos: Um currículo universitário tem N disciplinas com pré-requisitos. Dado o grafo de dependências, encontre uma ordem válida para cursar todas as disciplinas. Detecte se há dependência circular impossível.

  2. Pipeline de CI/CD: Dado um conjunto de jobs com dependências, determine quais jobs podem ser executados em paralelo em cada etapa. Calcule o tempo mínimo total se cada job tem uma duração conhecida (caminho crítico).

  3. Resolução de dependências com versões: Modifique a ordenação topológica para lidar com pacotes que têm múltiplas versões. Se dois pacotes dependem de versões diferentes do mesmo pacote, sinalize o conflito.

  4. Alien dictionary: Dada uma lista de palavras ordenadas em um alfabeto alienígena, deduza a ordem das letras do alfabeto usando ordenação topológica.

Veja Também