Ordenamiento topológico

Ordena un DAG para que toda flecha apunte hacia adelante: prerrequisitos primero. Existe si y solo si no hay ciclos.

Dos algoritmos, ambos conocidos

• Kahn (sabor BFS): quita repetidamente un nodo con in-degree 0, liberando a sus dependientes
• DFS (sabor profundidad): el inverso del orden de finalización
• Ambos O(V+E); ambos detectan ciclos (no existe orden)
• Otra vez: "¿cuál recorrido, más qué?"

Mira a Kahn pelar el grafo

Verde = listo (in-degree 0) · naranja = colocando · oscuro = bloqueado (muestra el in-degree restante). La frontera de nodos listos barre de izquierda a derecha.

Adivinar casi nunca funciona

12 aristas → 1 de cada ~741 órdenes aleatorios es válido. Ordenamiento topológico: válido siempre, O(V+E).

El orden no es único

• Un DAG es un orden parcial; un orden topológico es una extensión lineal
• Las tareas incomparables (sin camino entre ellas) pueden ir en cualquier sentido
• Kahn y DFS devuelven órdenes válidos distintos — ambos correctos
• Prueba la propiedad (toda arista hacia adelante), no una secuencia exacta

Para llevar

graphlib.TopologicalSorter viene con Python 3.9+ — incluido de fábrica. Sin orden válido ⇒ tus dependencias tienen un ciclo (seguido, ese es el hallazgo real). Sigue: los pesos rompen la suposición de "cada arista = un paso" → Dijkstra.