Topological sort ordena linearmente os vértices de um DAG (directed acyclic graph) para que cada aresta u->v tenha u antes de v. Ele responde "em que ordem posso fazer estas tarefas dadas suas dependências?"
Duas abordagens comuns: (remova repetidamente nós com grau de entrada 0) ou (reverse post-order). Uma ordenação válida 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']
Use para sistemas de compilação, agendamento de tarefas, pré-requisitos de cursos e resolução de dependências. Se o resultado for mais curto que V, o grafo tem um ciclo (sem ordem válida). A ordenação geralmente não é única.
Ordenação de dependência está em toda parte — compiladores, gerenciadores de pacotes, recálculo de planilhas, pipelines de CI.
Ordenação topológica também funciona como detecção de ciclo para grafos direcionados.
Reconhecer um problema como "ordenação sob restrições" e recorrer à ordenação topológica é um sinal forte de senioridade.