--- title: "Ordenação Topológica em Rust" url: "https://rustlang.com.br/algoritmos/topological-sort/" markdown_url: "https://rustlang.com.br/algoritmos/topological-sort.MD" description: "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." date: "2026-02-24" author: "Equipe Rust Brasil" --- # 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. 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 ```rust use std::collections::HashMap; /// Grafo direcionado acíclico (DAG). fn criar_dag() -> Vec> { // 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 | Caso | Tempo | Espaço | |---------|----------|----------| | Melhor | O(V + E) | O(V + E) | | Médio | O(V + E) | O(V + E) | | Pior | O(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 ```rust 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>) -> Result, &'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 ```rust 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>) -> Result, &'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>, v: usize, visitados: &mut HashSet, em_processamento: &mut HashSet, pilha: &mut Vec, ) -> 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 ```rust use std::collections::VecDeque; /// Encontra todas as ordenações topológicas possíveis. fn todas_ordenacoes(grafo: &Vec>) -> Vec> { 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>, grau_entrada: &mut Vec, usado: &mut Vec, atual: &mut Vec, resultados: &mut Vec>, 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**. ```rust use std::collections::VecDeque; /// Retorna os vértices agrupados por nível (paralelizáveis dentro do mesmo nível). fn topological_niveis(grafo: &Vec>) -> Option>> { 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ística | Kahn (BFS) | DFS Topológico | Todas as ordenações | |---------------------------|----------------------|----------------------|----------------------| | Complexidade de tempo | O(V + E) | O(V + E) | O(V! * (V + E)) | | Detecção de ciclos | Sim (natural) | Sim (com estado) | Sim | | Paralelismo natural | Sim (níveis) | Nao | Nao | | Múltiplas ordenações | Uma por execução | Uma por execução | Todas | | Implementação | Simples | Simples | Complexa | | Uso de memória | O(V) | O(V) + pilha recursão| O(V * num_resultados)| | Determinístico | Sim (com ordem fixa) | Depende da ordem DFS | Sim (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 - [`VecDeque` — Fila de duas pontas](/stdlib/vecdeque/) — usada na fila do algoritmo de Kahn - [`HashMap` — Mapa hash](/stdlib/hashmap/) — para grafos com vértices nomeados - [`Vec` — Vetor dinâmico](/stdlib/vec/) — para lista de adjacência e resultados - [Rust para DevOps](/artigos/rust-para-devops/) — aplicações de ordenação topológica em CI/CD - [Busca em Profundidade (DFS)](/algoritmos/dfs/) — base da abordagem DFS para topological sort - [Busca em Largura (BFS)](/algoritmos/bfs/) — base do algoritmo de Kahn