Overview
El ordenamiento topológico ordena los vértices de un DAG de modo que para cada arista u→v, u aparece antes que v.
Analogy
Como ordenar tareas con dependencias: necesitas completar los prerrequisitos antes del curso principal — el orden topológico da una secuencia válida.
Step-by-step
- Método 1 (Kahn): calcula in-degree de cada nodo
- Añade nodos con in-degree 0 a la cola
- Procesa: quita de la cola, reduce in-degree de vecinos
- Los nuevos in-degree 0 entran a la cola
- Método 2: DFS con postorden invertido
Visual
A→C, B→C, C→D
In-degree: A=0,B=0,C=2,D=1
Kahn: A,B → C → D
Common mistakes
- Intentar ordenar un grafo con ciclos → imposible
- Olvidar comprobar si todos los vértices fueron procesados (detecta ciclos)
Practice questions
- Implementa ambos métodos: Kahn y DFS
- Detecta si un plan de cursos tiene un ciclo