Calculadora de Orden Topológico

Pseudocódigo

Dos formulaciones estándar, ambas lineales. Kahn avanza desde los nodos sin prerrequisitos; la versión con DFS trabaja hacia atrás desde los tiempos de finalización.

// Kahn: quita repetidamente un nodo sin aristas entrantes
calcular gradoEntrada[v] para cada vértice
cola = todos los vértices con gradoEntrada 0
orden = []

mientras la cola no esté vacía:
    u = cola.sacar()
    orden.añadir(u)
    para cada arista (u, v):
        gradoEntrada[v] -= 1
        si gradoEntrada[v] == 0: cola.meter(v)

si orden.longitud < V: el grafo tiene un ciclo

// Variante DFS: inverso del orden de finalización
ejecutar DFS; apilar cada vértice al terminarlo
la pila, desapilada, es un orden topológico válido

Kahn tiene una ventaja práctica que conviene conocer: como detecta el ciclo contando cuántos nodos logró emitir, los vértices sobrantes son exactamente los implicados en un ciclo o situados aguas abajo de él. Eso lo hace mucho más útil que un booleano cuando necesitas informar de qué dependencias son circulares.

Ejemplo resuelto, paso a paso

Ejecuta Kahn sobre un pequeño grafo de dependencias de compilación, donde una arista X a Y significa que X debe compilarse antes que Y.

Grafo de ejemplo: Aristas dirigidas A a C, B a C, C a D y B a D.

1. Calcular los grados de entrada. A tiene 0, B tiene 0, C tiene 2 (desde A y B), D tiene 2 (desde C y B). La cola arranca con A y B.
2. Emitir A. El orden es [A]. Decrementa C a grado de entrada 1. Todavía no es cero, así que C no se encola.
3. Emitir B. El orden es [A, B]. Decrementa C a 0, así que C se encola. Decrementa D a 1.
4. Emitir C. El orden es [A, B, C]. Decrementa D a 0, así que D se encola.
5. Emitir D. El orden es [A, B, C, D]. La cola queda vacía y se emitieron los cuatro nodos, así que no existe ciclo.

Un orden válido es A, B, C, D. Fíjate en que B, A, C, D es igualmente válido: A y B no tienen prerrequisitos y su orden relativo no está restringido. El orden topológico no es único salvo que el grafo sea una única cadena, y por eso las pruebas deberían comprobar que cada arista apunta hacia adelante en lugar de comparar contra una secuencia esperada.

Complejidad y de dónde sale

Tiempo: O(V + E) · Espacio: O(V)

Calcular todos los grados de entrada requiere un recorrido de todas las aristas, O(E). Cada vértice se encola y desencola exactamente una vez, O(V). Cada arista se examina exactamente una vez, cuando se emite su origen y se decrementa el grado de entrada del destino, otro O(E). El espacio guarda el vector de grados de entrada, la cola y la lista de salida, todos O(V). La variante con DFS tiene las mismas cotas, con la pila de recursión en lugar de la cola. Ninguna puede mejorarse, ya que cualquier algoritmo correcto debe leer todas las aristas para conocer las restricciones.

Cuándo usar Ordenación Topológica y cuándo no

Kahn y DFS producen órdenes igualmente válidos. Elige según lo que necesites además de la ordenación.

Errores frecuentes

• Ejecutarlo sobre un grafo con ciclo y no darse cuenta. Un grafo cíclico no tiene ningún orden topológico. Kahn emitirá silenciosamente un orden parcial salvo que compares la longitud de la salida con V. Esa comprobación es la prueba de ciclo, y omitirla produce un orden de compilación plausible pero incompleto.
• Esperar una respuesta única. Dos nodos cualesquiera sin camino entre ellos pueden aparecer en cualquier orden. Comparar contra una secuencia fija hace fallar las pruebas sobre implementaciones correctas; comprueba en su lugar que cada arista apunta hacia adelante en la salida.
• Confundir la dirección de las aristas. Si una arista X a Y significa "X depende de Y", el orden topológico es el inverso del que quieres. Arregla el convenio una sola vez, en el punto donde se construye el grafo, en lugar de invertir la salida y confiar en que salga bien.
• Aplicarlo a grafos no dirigidos. El orden topológico solo está definido para grafos dirigidos acíclicos. Una arista no dirigida es un ciclo de dos, así que ningún grafo no dirigido con alguna arista tiene orden topológico.
• Recursión demasiado profunda en la variante DFS. Una cadena de dependencias de decenas de miles de nodos desbordará la pila de llamadas. Kahn es iterativo y no tiene ese límite, lo que es una razón por la que las herramientas de compilación tienden a preferirlo.

Preguntas frecuentes

¿Para qué sirve la ordenación topológica?

Ordena los vértices de un grafo dirigido acíclico de forma que cada arista apunte hacia adelante, lo que responde a la pregunta de en qué orden pueden ejecutarse unas tareas dadas sus dependencias. Planifica sistemas de compilación como Make y Gradle, resuelve el orden de instalación de paquetes, ordena asignaturas con prerrequisitos, secuencia la evaluación de celdas de hoja de cálculo y planifica la ejecución de instrucciones en compiladores.

¿Cuál es la diferencia entre Kahn y el enfoque con DFS?

Kahn quita repetidamente nodos con grado de entrada cero usando una cola, avanzando desde lo que no tiene prerrequisitos. El enfoque con DFS ejecuta una búsqueda en profundidad y emite los vértices en orden inverso de finalización. Ambos son O(V + E) y ambos dan órdenes válidos. Kahn es iterativo e informa de qué nodos están en ciclos; DFS es más corto pero recursivo.

¿Puede un grafo tener más de un orden topológico?

Casi siempre. Dos vértices cualesquiera sin camino dirigido entre ellos pueden aparecer en cualquier orden, así que un grafo con V vértices y pocas aristas puede tener muchísimas ordenaciones válidas. El orden es único solo cuando el grafo contiene un camino hamiltoniano, lo que para un DAG significa una única cadena que recorre todos los vértices.

¿Cómo se detecta un ciclo durante la ordenación topológica?

Con Kahn, cuenta los vértices emitidos: si salen menos de V, los restantes están en un ciclo o aguas abajo de él, porque ninguno llegó nunca a grado de entrada cero. Con la variante DFS, una arista de retroceso hacia un vértice que sigue en la pila de recursión demuestra un ciclo.

¿Cuál es la complejidad temporal de la ordenación topológica?

O(V + E) en tiempo y O(V) en espacio, tanto para Kahn como para la variante con DFS. Cada vértice se procesa una vez y cada arista se examina una vez. Es óptimo, ya que cualquier algoritmo debe como mínimo leer todas las aristas de dependencia.