Ordenamiento Topológico ordena los nodos de un grafo dirigido acíclico (DAG) de modo que cada nodo aparezca antes que todos sus descendientes. Es la formalización de “resuelve las dependencias antes de ejecutar”.

Si el grafo tiene ciclos, el ordenamiento topológico es imposible — esa es la base de la detección de ciclos en grafos dirigidos.

Cómo Funciona

1. Identifica todos los nodos con grado de entrada 0 (sin dependencias).
2. Procesa cada nodo de grado 0: añádelo al orden y elimina sus aristas salientes (reduciendo el grado de entrada de sus vecinos).
3. Repite hasta que no queden nodos de grado 0.
4. Verifica: si quedan nodos sin procesar, el grafo tiene ciclos.

Idea Clave

Un DAG siempre tiene al menos un nodo de grado de entrada 0 (un nodo sin dependencias). Al procesarlo y eliminar sus aristas, el subgrafo restante sigue siendo un DAG, así que podemos aplicar la misma lógica recursivamente.

Si al final del algoritmo quedan nodos sin procesar, significa que hay un ciclo — ningún nodo en el ciclo puede tener grado de entrada 0 porque todos dependen entre sí.

Ejemplo Trabajado

DAG de tareas:

A → B → D
│    ↓
└→ C → E

Grados de entrada iniciales:

• “A: 0 (sin dependencias)”
• “B: 1 (después de A)”
• “C: 1 (después de A)”
• “D: 1 (después de B)”
• “E: 1 (después de C)”

Procesamiento:

1. A (grado 0) → orden: [A]

   • Elimina aristas A→B, A→C
   • “Nuevos grados: B=0, C=0”

2. B (grado 0) → orden: [A, B]

   • Elimina arista B→D
   • “Nuevo grado: D=0”

3. C (grado 0) → orden: [A, B, C]

   • Elimina arista C→E
   • “Nuevo grado: E=0”

4. D (grado 0) → orden: [A, B, C, D]

5. E (grado 0) → orden: [A, B, C, D, E]

Resultado: A → B → C → D → E (otro orden válido: A → C → B → E → D). Observa el visualizador mostrar la cola de nodos procesables.

Casos Extremos y Trampas

• Grafo con ciclos — el algoritmo se detiene con nodos sin procesar. Eso es la detección de ciclos.
• Múltiples órdenes válidos — un DAG puede tener muchos ordenamientos topológicos. Cualquiera es válido.
• Nodo aislado — grado de entrada 0, se procesa inmediatamente.
• Grafo disperso — O(V + E) sigue siendo eficiente.

Comparación con DFS

Aplicaciones

• Scheduling de tareas — compiladores, pipelines de CI/CD
• “Build systems — Make, Bazel: orden de compilación”
• Dependencias de paquetes — npm, pip, apt resuelven órdenes de instalación
• Course scheduling — orden de materias con prerrequisitos
• Resolución de símbolos — enlazado de código

Trayectoria de Práctica

1. Aplica Kahn’s algorithm al DAG del visualizador; registra la cola después de cada extracción.
2. Modifica el algoritmo para retornar cualquier orden válido; prueba en un DAG con múltiples caminos.
3. Agrega detección de ciclos: si |orden| < V, reporta ciclo y retorna el ciclo encontrado.
4. Diseña un DAG donde A → B → C y A → C; ¿cuántos órdenes topológicos válidos existen?
5. Investiga topological sort en Makefiles: ¿por qué Make requiere un DAG de dependencias?