Algoritmo de Kahn: ordenación topológica con BFS
Calcule los grados de entrada de todos los nodos, encole los nodos con grado de entrada cero y procese la cola para producir un orden topológico y detectar ciclos.
Algoritmo de Kahn: ordenación topológica con BFS 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 la ordenación topológica?
Una ordenación topológica de un grafo acíclico dirigido (DAG) es una ordenación de sus nodos tal que cada arista dirigida u → v indica que u aparece antes que v en la ordenación. Representa un orden de ejecución válido para tareas con dependencias, como sistemas de compilación, planificación de cursos o gestión de paquetes. Solo los DAG tienen ordenaciones topológicas válidas; un ciclo lo hace imposible.
Algoritmo de Kahn: idea central
El algoritmo de Kahn es un enfoque basado en BFS para la ordenación topológica. La idea clave es que un nodo con grado de entrada 0 (sin prerrequisitos) puede colocarse primero en la ordenación. Después de colocarlo, elimínelo y disminuya el grado de entrada de sus vecinos. Los nuevos nodos con grado de entrada cero pasan a estar disponibles. Repita el proceso hasta colocar todos los nodos o detectar un ciclo (quedan nodos con grado de entrada distinto de cero).
Cálculo del grado de entrada
Primero, construya la lista de adyacencia y calcule el grado de entrada (el número de aristas entrantes) de cada nodo. Los nodos con grado de entrada 0 son los puntos de partida: no tienen dependencias. Para un grafo con aristas [(0,1),(0,2),(1,3),(2,3)], los grados de entrada son: 0→0, 1→1, 2→1, 3→2. Solo el nodo 0 comienza con grado de entrada 0.
from collections import deque, defaultdict
def compute_in_degree(n, edges):
in_degree = [0] * n
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
in_degree[v] += 1
return graph, in_degree
graph, ind = compute_in_degree(4, [(0,1),(0,2),(1,3),(2,3)])
print('In-degrees:', ind) # [0, 1, 1, 2]Implementación del algoritmo de Kahn
Introduzca todos los nodos con grado de entrada cero en una cola. Procese cada nodo: añádalo al resultado; después, para cada vecino, disminuya su grado de entrada e introdúzcalo en la cola si llega a 0. Si la lista de resultados contiene menos nodos que el grafo, existe un ciclo: algunos nodos nunca podrían retirarse de la cola.
from collections import deque, defaultdict
def kahn_topological_sort(n, edges):
graph = defaultdict(list)
in_degree = [0] * n
for u, v in edges:
graph[u].append(v)
in_degree[v] += 1
queue = deque(i for i in range(n) if in_degree[i] == 0)
order = []
while queue:
node = queue.popleft()
order.append(node)
for nxt in graph[node]:
in_degree[nxt] -= 1
if in_degree[nxt] == 0:
queue.append(nxt)
if len(order) == n:
return order # valid topological sort
return [] # cycle detected
print(kahn_topological_sort(4, [(0,1),(0,2),(1,3),(2,3)]))Detección de ciclos mediante Kahn
El algoritmo de Kahn ofrece detección de ciclos sin coste adicional: si len(order) < n, algunos nodos nunca se añadieron a la cola porque su grado de entrada nunca llegó a 0; forman parte de un ciclo. Esto es más sencillo que mantener un arreglo de visitados codificado por colores. Devuelva una lista vacía para indicar que existe un ciclo.
# Cyclic graph: 0->1->2->0
edges_cycle = [(0,1),(1,2),(2,0)]
result = kahn_topological_sort(3, edges_cycle)
print(result) # [] (cycle detected)
# Acyclic graph
edges_dag = [(0,1),(1,2)]
result = kahn_topological_sort(3, edges_dag)
print(result) # [0, 1, 2]Complejidad temporal y espacial
El algoritmo de Kahn procesa cada nodo una vez (se retira de la cola una vez) y cada arista una vez (su grado de entrada se disminuye una vez). Complejidad temporal: O(V + E). Espacio: O(V + E) para la lista de adyacencia y el arreglo de grados de entrada, además de O(V) para la cola. Esto es óptimo: como mínimo, debe leer todos los nodos y aristas para producir una ordenación válida.
Ordenación topológica lexicográficamente menor
El algoritmo de Kahn con un min-heap en lugar de una cola produce la ordenación topológica lexicográficamente menor. Sustituya deque por heapq: inserte (node) y procese siempre primero el nodo disponible más pequeño. Esto garantiza la ordenación válida lexicográficamente menor entre todas las ordenaciones topológicas posibles.
import heapq
from collections import defaultdict
def kahn_lex_order(n, edges):
graph = defaultdict(list)
in_degree = [0] * n
for u, v in edges:
graph[u].append(v)
in_degree[v] += 1
heap = [i for i in range(n) if in_degree[i] == 0]
heapq.heapify(heap)
order = []
while heap:
node = heapq.heappop(heap)
order.append(node)
for nxt in graph[node]:
in_degree[nxt] -= 1
if in_degree[nxt] == 0:
heapq.heappush(heap, nxt)
return order if len(order) == n else []
print(kahn_lex_order(6, [(5,2),(5,0),(4,0),(4,1),(2,3),(3,1)]))Aplicación: Course Schedule I
Course Schedule (LeetCode 207): dados n cursos y sus prerrequisitos, ¿puede completar todos los cursos? Modele los prerrequisitos como aristas dirigidas y compruebe si existe una ordenación topológica válida (es decir, si no hay ningún ciclo). Devuelva True si el algoritmo de Kahn produce una ordenación de longitud n y False si se detecta un ciclo.
from collections import deque, defaultdict
def canFinish(numCourses, prerequisites):
graph = defaultdict(list)
in_degree = [0] * numCourses
for a, b in prerequisites: # b must be taken before a
graph[b].append(a)
in_degree[a] += 1
queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
count = 0
while queue:
node = queue.popleft()
count += 1
for nxt in graph[node]:
in_degree[nxt] -= 1
if in_degree[nxt] == 0:
queue.append(nxt)
return count == numCourses
print(canFinish(2, [[1,0]])) # True
print(canFinish(2, [[1,0],[0,1]])) # False (cycle)Aplicación: Course Schedule II
Course Schedule II (LeetCode 210): devuelva el orden real en el que debe realizar los cursos. Igual que antes, pero devuelva la lista order en lugar de un booleano. Si existe un ciclo, devuelva una lista vacía. Esto utiliza directamente la salida del algoritmo de Kahn como respuesta.
from collections import deque, defaultdict
def findOrder(numCourses, prerequisites):
graph = defaultdict(list)
in_degree = [0] * numCourses
for a, b in prerequisites:
graph[b].append(a)
in_degree[a] += 1
queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
order = []
while queue:
node = queue.popleft()
order.append(node)
for nxt in graph[node]:
in_degree[nxt] -= 1
if in_degree[nxt] == 0:
queue.append(nxt)
return order if len(order) == numCourses else []
print(findOrder(4, [[1,0],[2,0],[3,1],[3,2]]))Programación de tareas en paralelo
Un uso más avanzado: dadas tareas con dependencias, encuentre el número mínimo de «rondas» necesarias si las tareas sin dependencias pueden ejecutarse en paralelo. Procese el algoritmo de Kahn por niveles, de forma similar al recorrido BFS por niveles: introduzca todos los nodos con grado de entrada cero en la cola, procese toda la cola actual como una ronda y, después, introduzca los nodos recién liberados como la ronda siguiente. Cuente las rondas.
from collections import deque, defaultdict
def min_rounds(n, edges):
graph = defaultdict(list)
in_degree = [0] * n
for u, v in edges:
graph[u].append(v)
in_degree[v] += 1
queue = deque(i for i in range(n) if in_degree[i] == 0)
rounds = 0
while queue:
rounds += 1
for _ in range(len(queue)): # process current level
node = queue.popleft()
for nxt in graph[node]:
in_degree[nxt] -= 1
if in_degree[nxt] == 0:
queue.append(nxt)
return rounds
print(min_rounds(4, [(0,2),(1,2),(2,3)])) # 3Ordenación topológica y programación dinámica en DAG
La ordenación topológica permite aplicar programación dinámica en DAG: procese los nodos en orden topológico y, al calcular dp[v], todos los valores dp[u] de sus predecesores ya son definitivos. Esto combina la ordenación topológica con la programación dinámica para problemas como la ruta más larga en un DAG, el coste mínimo para llegar a todos los nodos o el beneficio máximo de una cadena de dependencias. La ordenación garantiza que el valor de programación dinámica de cada nodo se calcule exactamente una vez, después de todas sus dependencias.
from collections import deque, defaultdict
def longest_path_dag(V, edges):
graph = defaultdict(list)
in_degree = [0] * V
for u, v, w in edges:
graph[u].append((v, w))
in_degree[v] += 1
queue = deque(i for i in range(V) if in_degree[i] == 0)
dp = [0] * V
while queue:
u = queue.popleft()
for v, w in graph[u]:
dp[v] = max(dp[v], dp[u] + w)
in_degree[v] -= 1
if in_degree[v] == 0: queue.append(v)
return max(dp)
print(longest_path_dag(4, [(0,1,3),(0,2,2),(1,3,4),(2,3,1)])) # 7Comprobación rápida
Compruebe su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.
Resumen de la lección
En esta lección ha aprendido: el algoritmo de Kahn calcula la ordenación topológica eliminando iterativamente mediante BFS los nodos con grado de entrada cero, la detección de ciclos no tiene coste adicional: si len(order) < n, existe un ciclo y sustituir la cola por un min-heap produce la ordenación topológica lexicográficamente menor. A continuación, explorará la ordenación topológica basada en DFS y postorden como alternativa al algoritmo de Kahn.
Preguntas frecuentes
¿La lección «Algoritmo de Kahn: ordenación topológica con BFS» es gratis?
Sí — el texto completo de «Algoritmo de Kahn: ordenación topológica con BFS» 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 «Algoritmo de Kahn: ordenación topológica con BFS»?
Calcule los grados de entrada de todos los nodos, encole los nodos con grado de entrada cero y procese la cola para producir un orden topológico y detectar ciclos. 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 «Algoritmo de Kahn: ordenación topológica con BFS»?
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
- Algoritmo de Kahn: ordenación topológica con BFS
- Ordenación topológica con DFS en postorden
- Course Schedule I y II
- Componentes fuertemente conexas con Kosaraju