Ordenamiento topológico ordena linealmente los vértices de un DAG (grafo dirigido acíclico) de manera que cada arista u->v tenga u antes que v. Responde la pregunta "¿en qué orden puedo realizar estas tareas dadas sus dependencias?"
Dos enfoques comunes: (eliminar repetidamente nodos con grado de entrada 0) o (orden inverso post-orden). Un ordenamiento válido existe .
from collections import deque
def topo_sort(graph):
indeg = {u: 0 for u in graph}
for u in graph:
for v in graph[u]:
indeg[v] += 1 # count incoming edges
queue = deque([u for u in indeg if indeg[u] == 0])
order = []
while queue:
u = queue.popleft()
order.append(u)
for v in graph[u]:
indeg[v] -= 1 # "remove" the edge
if indeg[v] == 0:
queue.append(v)
return order if len(order) == len(graph) else None # None -> cycle
topo_sort({'shirt': ['tie'], 'tie': ['jacket'], 'jacket': []})
# -> ['shirt', 'tie', 'jacket']
Úsalo para sistemas de compilación, planificación de tareas, requisitos previos de cursos y resolución de dependencias. Si el resultado es más corto que V, el grafo tiene un ciclo (sin orden válido). El ordenamiento generalmente no es único.
El ordenamiento de dependencias está en todas partes — compiladores, gestores de paquetes, recalcificación de hojas de cálculo, pipelines de CI.
El ordenamiento topológico sirve además para detectar ciclos en grafos dirigidos.
Reconocer un problema como "ordenamiento bajo restricciones" y recurrir al ordenamiento topológico es una señal sólida de nivel senior.