Ordenamiento Topológico
Última actualización
Un ordenamiento topológico de un grafo acíclico dirigido (DAG) es un orden lineal de sus nodos tal que para cada arista u → v, u aparece antes que v. Responde preguntas como «¿en qué orden puedo ejecutar estas tareas para que cada prerrequisito termine primero?». Pulsa reproducir arriba para ver cómo el algoritmo de Kahn extrae los nodos en un orden válido.
El algoritmo de Kahn toma repetidamente un nodo sin aristas entrantes restantes (grado de entrada 0), lo añade al orden y elimina sus aristas salientes, lo que puede liberar nuevos nodos con grado de entrada 0. Solo funciona sobre un DAG: si existe un ciclo, algunos nodos nunca llegan a grado de entrada 0 y no existe un orden válido. Se ejecuta en tiempo O(V + E).
Complejidad temporal y espacial
| Medida | Complejidad | Notas |
|---|---|---|
| Tiempo | O(V + E) | Cada nodo se emite una vez, cada arista se elimina una vez |
| Espacio | O(V) | Conteos de grado de entrada + conjunto listo + orden |
| Requiere | Un DAG | Los ciclos no tienen ordenamiento topológico |
| Resultado | No único | Pueden existir muchos órdenes válidos |
Paso a paso (algoritmo de Kahn)
| Paso | Qué ocurre |
|---|---|
| 1 | Calcular el grado de entrada (número de aristas entrantes) de cada nodo. |
| 2 | Reunir todos los nodos con grado de entrada 0 en un conjunto listo. |
| 3 | Tomar un nodo listo y añadirlo al orden de salida. |
| 4 | Decrementar el grado de entrada de cada uno de sus sucesores. |
| 5 | Todo sucesor que llegue a grado de entrada 0 se une al conjunto listo. |
| 6 | Repetir hasta que el conjunto listo esté vacío. |
Ejemplo resuelto
Ordenando el DAG con aristas A→C, B→C, C→D, C→E, D→F, E→F (grados de entrada iniciales A:0 B:0 C:2 D:1 E:1 F:2):
| Paso | Conjunto listo | Orden | Acción |
|---|---|---|---|
| 0 | {A, B} | [] | A y B empiezan con grado de entrada 0, así que ambos están listos. |
| 1 | {B} | [A] | Emitir A; su arista A→C baja el grado de entrada de C de 2 → 1. |
| 2 | {C} | [A, B] | Emitir B; su arista B→C baja C de 1 → 0, así que C queda listo. |
| 3 | {D, E} | [A, B, C] | Emitir C; las aristas C→D y C→E bajan D y E a 0, ambos quedan listos. |
| 4 | {E} | [A, B, C, D] | Emitir D; su arista D→F baja el grado de entrada de F de 2 → 1. |
| 5 | {F} | [A, B, C, D, E] | Emitir E; su arista E→F baja F de 1 → 0, así que F queda listo. |
| 6 | {} | [A, B, C, D, E, F] | Emitir F; el conjunto listo está vacío y los 6 nodos están ordenados: listo. |
Cuándo usar el ordenamiento topológico
| Úsalo cuando | Evítalo cuando |
|---|---|
| Necesitas un orden que respete dependencias (pasos de compilación, instalación de paquetes, prerrequisitos de cursos). | El grafo no es dirigido: el orden topológico solo se define para grafos dirigidos. |
| El grafo es un DAG y quieres cualquier orden lineal válido. | El grafo puede contener ciclos y aun así necesitas un orden total (no existe ninguno). |
| Quieres detectar ciclos de forma barata: un ordenamiento topológico fallido demuestra que existe uno. | Necesitas el orden más corto u óptimo según algún peso; el ordenamiento topológico simple ignora los pesos. |
Procesarás el orden una sola vez en O(V + E). | Las aristas cambian constantemente y debes reordenar en cada actualización, donde encaja mejor una estructura incremental. |
Código de Topological Sort
Una implementación limpia y ejecutable de Topological Sort en Python, JavaScript, Java, C++, C. Elige un lenguaje, copia el código o ábrelo ya cargado en el Playground de Coddy.
Código de Topological Sort en 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 en 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 en 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 en 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 en 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}Preguntas frecuentes sobre el ordenamiento topológico
¿Para qué sirve un ordenamiento topológico?
Ordena las tareas de modo que cada dependencia venga antes de lo que la necesita. Usos reales incluyen sistemas de compilación y gestores de paquetes (compilar dependencias primero), la planificación de cursos con prerrequisitos y el orden de evaluación de fórmulas en hojas de cálculo.
¿Cuál es la complejidad temporal del ordenamiento topológico?
Tanto el algoritmo de Kahn como el enfoque basado en DFS se ejecutan en tiempo
O(V + E), ya que cada nodo se procesa una vez y cada arista se examina una vez. Usan O(V) de espacio adicional.¿Por qué el ordenamiento topológico requiere un DAG?
Un ciclo dirigido crea una contradicción: si
a debe venir antes de b y b debe venir antes de a, ningún orden lineal satisface ambas condiciones. Por eso existe un ordenamiento topológico si y solo si el grafo es un grafo acíclico dirigido. El algoritmo de Kahn detecta un ciclo cuando termina antes de emitir todos los nodos.¿Cuál es la diferencia entre el algoritmo de Kahn y el ordenamiento topológico por DFS?
El algoritmo de Kahn es iterativo y parecido a BFS: elimina repetidamente los nodos con grado de entrada 0, lo que hace explícitas la detección de ciclos y la ordenación. El enfoque DFS visita los nodos recursivamente y antepone cada uno al orden cuando su recursión termina, produciendo el inverso de los tiempos de finalización. Ambos son
O(V + E); el de Kahn evita la recursión profunda y expone el conjunto listo de forma natural, mientras que el DFS suele ser más corto de escribir.¿Cuándo debo usar el ordenamiento topológico en lugar de un ordenamiento normal?
Usa el ordenamiento topológico cuando el orden esté definido por dependencias entre elementos en lugar de por una clave comparable. Un ordenamiento por comparación como el mergesort
O(n log n) ordena por valor; el ordenamiento topológico ordena por aristas de «debe venir antes» y, a diferencia de un ordenamiento por comparación, puede producir muchas respuestas válidas para la misma entrada.¿Es único el resultado de un ordenamiento topológico?
Normalmente no. Siempre que dos o más nodos estén listos (grado de entrada 0) al mismo tiempo, puedes emitirlos en cualquier orden, por lo que la mayoría de los DAG admiten varios ordenamientos topológicos válidos. El orden es único solo cuando hay exactamente un nodo listo en cada paso, lo que ocurre cuando el DAG forma una única cadena (un camino hamiltoniano).
Recursos relacionados
Más visualizaciones
