Motivation
Lección 2 de 9 del curso Ordenamiento Topológico - Algoritmos de Grafos de Coddy.
Un orden topológico solo existe cuando el grafo no tiene ciclos. Construimos uno con el algoritmo de Kahn, el cual elimina repetidamente un vértice que no tiene aristas entrantes restantes.
¿Por qué aprender el Ordenamiento Topológico?
- Ordenamiento con restricciones: los sistemas de compilación, la programación de tareas, los prerrequisitos de cursos y el recálculo de hojas de cálculo dependen de él.
- Detección de ciclos: si no puedes ordenar cada vértice, el grafo debe contener un ciclo.
- Base para algoritmos de DAG: los caminos más cortos y más largos en un DAG se calculan en orden topológico.
Pueden existir muchos órdenes válidos. Para obtener una respuesta predecible, siempre eliminamos el vértice con el número más pequeño cuyo grado de entrada es 0.
Pruébalo tú mismo
Esta lección no incluye un desafío de código.
Ponte a pruebaEsta lección incluye un breve cuestionario. Empieza la lección para responderlo y registrar tu progreso.
