Ordenación topológica con el algoritmo de Kahn
Ordene tareas que dependen de otras
Ordenación topológica con el algoritmo de Kahn es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 1 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Coding Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Coding Interview Prep incluye 4 lecciones en total.
Qué es un orden topológico
Un orden topológico enumera todos los nodos de un grafo dirigido de modo que cada arista apunte de uno anterior a otro posterior. Piense en colocar primero las tareas de las que dependen otras tareas.
Solo se permiten DAG
Esto solo funciona en un DAG, es decir, un grafo dirigido acíclico. Si existe un ciclo, ningún orden válido puede satisfacer todas las dependencias.
La idea del grado de entrada
El algoritmo de Kahn se basa en el grado de entrada: cuántas aristas apuntan hacia un nodo. Un nodo con grado de entrada cero no tiene dependencias pendientes.
Contar todos los grados de entrada
Primera pasada: recorra todas las aristas y cuente cuántas veces aparece cada nodo como destino. Así obtiene el grado de entrada de cada nodo.
indeg = [0] * n
for u in range(n):
for v in adj[u]:
indeg[v] += 1Inicializar la cola de nodos listos
Todo nodo con grado de entrada cero está listo de inmediato, así que introdúzcalos todos en una cola para empezar.
from collections import deque
q = deque(u for u in range(n) if indeg[u] == 0)Procesar un nodo
Extraiga un nodo listo y añádalo a su orden. Ahora es seguro porque ninguna tarea pendiente depende de él.
u = q.popleft()
order.append(u)Liberar sus vecinos
Para cada vecino, reduzca su grado de entrada en uno. Cuando un vecino llega a cero, está listo y se incorpora a la cola.
for v in adj[u]:
indeg[v] -= 1
if indeg[v] == 0:
q.append(v)Repetir hasta vaciar la cola
Siga extrayendo nodos y liberando vecinos hasta que la cola se vacíe. El orden crece con un nodo seguro cada vez hasta colocar todos los nodos.
Detectar un ciclo sin coste adicional
Si el orden final contiene menos de n nodos, un ciclo ha dejado atrapados a los demás. El algoritmo de Kahn permite detectar ciclos sin coste adicional.
if len(order) < n:
print('cycle exists')El tiempo de ejecución
Cada nodo y cada arista se recorren una vez, así que el algoritmo de Kahn se ejecuta en O(V + E). Esto permite trabajar con grafos que tienen millones de aristas.
Muchos órdenes válidos
Cuando hay varios nodos listos a la vez, cualquiera puede ir después. Por eso un DAG suele tener muchos órdenes topológicos válidos, no solo uno.
Comprobación rápida
Termina el algoritmo de Kahn, pero el orden tiene menos de n nodos. ¿Qué significa?
Repaso: algoritmo de Kahn
Cuente los grados de entrada, introduzca los ceros en una cola, extraiga un nodo, reduzca los grados de sus vecinos y repita. Así se realiza un ordenamiento topológico claro en O(V+E). 🚀
Preguntas frecuentes
¿La lección «Ordenación topológica con el algoritmo de Kahn» es gratis?
Sí — el texto completo de «Ordenación topológica con el algoritmo de Kahn» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Coding Interview Prep, actualiza a CoddyKit PRO. El curso de Coding Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «Ordenación topológica con el algoritmo de Kahn»?
Ordene tareas que dependen de otras Practicas Coding Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar Coding Interview Prep?
No se requiere experiencia previa. Coding Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 1 de 4.
¿Cuánto tiempo toma la lección «Ordenación topológica con el algoritmo de Kahn»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de Coding Interview Prep?
Sí. Cada lección de Coding Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- Ordenación topológica con el algoritmo de Kahn
- Detecte ciclos en grafos dirigidos
- Componentes fuertemente conexas
- Puentes y puntos de articulación