Ordenação Topológica
Última atualização
Uma ordenação topológica de um grafo acíclico dirigido (DAG) é uma ordenação linear de seus nós tal que, para cada aresta u → v, u vem antes de v. Ela responde perguntas como «em que ordem posso executar estas tarefas para que cada pré-requisito termine primeiro?». Pressione reproduzir acima para ver o algoritmo de Kahn retirar os nós em uma ordem válida.
O algoritmo de Kahn pega repetidamente um nó sem arestas de entrada restantes (grau de entrada 0), acrescenta-o à ordem e remove suas arestas de saída, o que pode liberar novos nós com grau de entrada 0. Ele só funciona em um DAG: se existir um ciclo, alguns nós nunca chegam a grau de entrada 0 e não há ordem válida. Executa em tempo O(V + E).
Complexidade de tempo e espaço
| Medida | Complexidade | Notas |
|---|---|---|
| Tempo | O(V + E) | Cada nó é emitido uma vez, cada aresta é removida uma vez |
| Espaço | O(V) | Contagens de grau de entrada + conjunto pronto + ordem |
| Requer | Um DAG | Ciclos não têm ordenação topológica |
| Resultado | Não único | Muitas ordens válidas podem existir |
Passo a passo (algoritmo de Kahn)
| Passo | O que acontece |
|---|---|
| 1 | Calcular o grau de entrada (número de arestas de entrada) de cada nó. |
| 2 | Reunir todos os nós com grau de entrada 0 em um conjunto pronto. |
| 3 | Pegar um nó pronto e acrescentá-lo à ordem de saída. |
| 4 | Decrementar o grau de entrada de cada um de seus sucessores. |
| 5 | Todo sucessor que chegar a grau de entrada 0 entra no conjunto pronto. |
| 6 | Repetir até o conjunto pronto ficar vazio. |
Exemplo resolvido
Ordenando o DAG com arestas A→C, B→C, C→D, C→E, D→F, E→F (graus de entrada iniciais A:0 B:0 C:2 D:1 E:1 F:2):
| Passo | Conjunto pronto | Ordem | Ação |
|---|---|---|---|
| 0 | {A, B} | [] | A e B começam com grau de entrada 0, então ambos estão prontos. |
| 1 | {B} | [A] | Emitir A; sua aresta A→C reduz o grau de entrada de C de 2 → 1. |
| 2 | {C} | [A, B] | Emitir B; sua aresta B→C reduz C de 1 → 0, então C fica pronto. |
| 3 | {D, E} | [A, B, C] | Emitir C; as arestas C→D e C→E reduzem D e E a 0, ambos ficam prontos. |
| 4 | {E} | [A, B, C, D] | Emitir D; sua aresta D→F reduz o grau de entrada de F de 2 → 1. |
| 5 | {F} | [A, B, C, D, E] | Emitir E; sua aresta E→F reduz F de 1 → 0, então F fica pronto. |
| 6 | {} | [A, B, C, D, E, F] | Emitir F; o conjunto pronto está vazio e os 6 nós estão ordenados: concluído. |
Quando usar a ordenação topológica
| Use quando | Evite quando |
|---|---|
| Você precisa de uma ordem que respeite dependências (etapas de compilação, instalação de pacotes, pré-requisitos de cursos). | O grafo é não dirigido: a ordem topológica só é definida para grafos dirigidos. |
| O grafo é um DAG e você quer qualquer ordenação linear válida. | O grafo pode conter ciclos e você ainda precisa de uma ordem total (não existe nenhuma). |
| Você quer detectar ciclos de forma barata: uma ordenação topológica que falha prova que existe um. | Você precisa da ordem mais curta ou ótima segundo algum peso; a ordenação topológica simples ignora pesos. |
Você processará a ordem uma única vez em O(V + E). | As arestas mudam constantemente e você precisa reordenar a cada atualização, onde uma estrutura incremental encaixa melhor. |
Código de Topological Sort
Uma implementação limpa e executável de Topological Sort em Python, JavaScript, Java, C++, C. Escolha uma linguagem, copie o código ou abra-o já carregado no Playground da Coddy.
Código de Topological Sort em Python
Python
1from collections import deque2
3
4def topological_sort(graph):5 # Kahn's algorithm: repeatedly remove nodes with no incoming edges6 in_degree = {node: 0 for node in graph}7 for node in graph:8 for neighbor in graph[node]:9 in_degree[neighbor] += 110 queue = deque(node for node in graph if in_degree[node] == 0)11 order = []12 while queue:13 node = queue.popleft()14 order.append(node)15 for neighbor in graph[node]:16 in_degree[neighbor] -= 117 if in_degree[neighbor] == 0:18 queue.append(neighbor)19 if len(order) != len(graph):20 raise ValueError("Graph has a cycle, no topological order")21 return order22
23
24graph = {25 "shirt": ["tie", "jacket"],26 "tie": ["jacket"],27 "pants": ["shoes", "jacket"],28 "socks": ["shoes"],29 "shoes": [],30 "jacket": [],31}32
33print(" -> ".join(topological_sort(graph)))Código de Topological Sort em JavaScript
JavaScript
1const graph = {2 A: ["C"],3 B: ["C", "D"],4 C: ["E"],5 D: ["F"],6 E: ["F"],7 F: [],8};9
10// Kahn algorithm: repeatedly take a node with no incoming edges11function topologicalSort() {12 const inDegree = {};13 for (const node in graph) inDegree[node] = 0;14 for (const node in graph) {15 for (const next of graph[node]) inDegree[next]++;16 }17 const queue = Object.keys(inDegree).filter((n) => inDegree[n] === 0);18 const order = [];19 while (queue.length > 0) {20 const node = queue.shift();21 order.push(node);22 for (const next of graph[node]) {23 if (--inDegree[next] === 0) queue.push(next);24 }25 }26 if (order.length !== Object.keys(graph).length) {27 throw new Error("Graph has a cycle");28 }29 return order;30}31
32console.log("Topological order:", topologicalSort().join(" -> "));Código de Topological Sort em Java
Java
1import java.util.ArrayDeque;2import java.util.List;3import java.util.Queue;4
5public class Main {6 public static void main(String[] args) {7 int n = 6;8 // DAG: an edge u -> v means u must come before v9 List<List<Integer>> adj = List.of(10 List.of(2),11 List.of(2, 3),12 List.of(4),13 List.of(4),14 List.of(5),15 List.of()16 );17 int[] inDegree = new int[n];18 for (List<Integer> next : adj) {19 for (int v : next) inDegree[v]++;20 }21
22 // Kahn: start from every node with no prerequisites23 Queue<Integer> queue = new ArrayDeque<>();24 for (int i = 0; i < n; i++) {25 if (inDegree[i] == 0) queue.add(i);26 }27
28 StringBuilder order = new StringBuilder("Topological order:");29 while (!queue.isEmpty()) {30 int node = queue.poll();31 order.append(" ").append(node);32 for (int next : adj.get(node)) {33 if (--inDegree[next] == 0) queue.add(next);34 }35 }36 System.out.println(order);37 }38}Código de Topological Sort em C++
C++
1#include <iostream>2#include <queue>3#include <vector>4
5int main() {6 // Directed acyclic graph: adj[u] lists nodes that depend on u7 std::vector<std::vector<int>> adj = {8 {}, // 09 {}, // 110 {3}, // 2 -> 311 {1}, // 3 -> 112 {0, 1}, // 4 -> 0, 113 {0, 2}, // 5 -> 0, 214 };15 int n = static_cast<int>(adj.size());16 std::vector<int> inDegree(n, 0);17 for (const auto& neighbors : adj) {18 for (int v : neighbors) ++inDegree[v];19 }20 // Kahn's algorithm: start from nodes with no incoming edges21 std::queue<int> ready;22 for (int u = 0; u < n; ++u) {23 if (inDegree[u] == 0) ready.push(u);24 }25 std::cout << "Topological order: ";26 while (!ready.empty()) {27 int u = ready.front();28 ready.pop();29 std::cout << u << " ";30 // Removing u unlocks neighbors whose in-degree drops to 031 for (int v : adj[u]) {32 if (--inDegree[v] == 0) ready.push(v);33 }34 }35 std::cout << "\n";36 return 0;37}Código de Topological Sort em C
C
1#include <stdio.h>2
3#define N 64
5int main(void) {6 // Directed acyclic graph: adj[u][v] = 1 means an edge u -> v7 int adj[N][N] = {0};8 adj[2][3] = 1;9 adj[3][1] = 1;10 adj[4][0] = 1;11 adj[4][1] = 1;12 adj[5][0] = 1;13 adj[5][2] = 1;14 int inDegree[N] = {0};15 for (int u = 0; u < N; u++) {16 for (int v = 0; v < N; v++) inDegree[v] += adj[u][v];17 }18 // Kahn's algorithm: start from nodes with no incoming edges19 int queue[N];20 int head = 0, tail = 0;21 for (int u = 0; u < N; u++) {22 if (inDegree[u] == 0) queue[tail++] = u;23 }24 printf("Topological order: ");25 while (head < tail) {26 int u = queue[head++];27 printf("%d ", u);28 // Removing u unlocks neighbors whose in-degree drops to 029 for (int v = 0; v < N; v++) {30 if (adj[u][v] && --inDegree[v] == 0) queue[tail++] = v;31 }32 }33 printf("\n");34 return 0;35}Perguntas frequentes sobre a ordenação topológica
Para que serve uma ordenação topológica?
Ela ordena as tarefas de modo que cada dependência venha antes daquilo que precisa dela. Usos reais incluem sistemas de compilação e gerenciadores de pacotes (compilar dependências primeiro), o agendamento de cursos com pré-requisitos e a ordem de avaliação de fórmulas em planilhas.
Qual é a complexidade de tempo da ordenação topológica?
Tanto o algoritmo de Kahn quanto a abordagem baseada em DFS executam em tempo
O(V + E), pois cada nó é processado uma vez e cada aresta é examinada uma vez. Eles usam O(V) de espaço adicional.Por que a ordenação topológica exige um DAG?
Um ciclo dirigido cria uma contradição: se
a deve vir antes de b e b deve vir antes de a, nenhuma ordem linear satisfaz ambas. Por isso, uma ordenação topológica existe se e somente se o grafo for um grafo acíclico dirigido. O algoritmo de Kahn detecta um ciclo quando termina antes de emitir todos os nós.Qual é a diferença entre o algoritmo de Kahn e a ordenação topológica por DFS?
O algoritmo de Kahn é iterativo e semelhante ao BFS: ele remove repetidamente os nós com grau de entrada 0, tornando explícitas a detecção de ciclos e a ordenação. A abordagem DFS visita os nós recursivamente e antepõe cada um à ordem quando sua recursão termina, produzindo o inverso dos tempos de finalização. Ambos são
O(V + E); o de Kahn evita recursão profunda e expõe o conjunto pronto naturalmente, enquanto o DFS costuma ser mais curto de escrever.Quando devo usar a ordenação topológica em vez de uma ordenação normal?
Use a ordenação topológica quando a ordem for definida por dependências entre itens em vez de por uma chave comparável. Uma ordenação por comparação como o mergesort
O(n log n) ordena por valor; a ordenação topológica ordena por arestas de «deve vir antes» e, ao contrário de uma ordenação por comparação, pode produzir muitas respostas válidas para a mesma entrada.O resultado de uma ordenação topológica é único?
Normalmente não. Sempre que dois ou mais nós estiverem prontos (grau de entrada 0) ao mesmo tempo, você pode emiti-los em qualquer ordem, então a maioria dos DAGs admite várias ordenações topológicas válidas. A ordem é única apenas quando há exatamente um nó pronto em cada passo, o que ocorre quando o DAG forma uma única cadeia (um caminho hamiltoniano).
Recursos relacionados
Mais visualizações
