Topological sort ordina linearmente i vertici di un DAG (directed acyclic graph) così che ogni arco u->v abbia u prima di v. Risponde alla domanda "in quale ordine posso fare questi compiti dati i loro vincoli di dipendenza?"
Due approcci comuni: (rimuovere ripetutamente i nodi con in-degree 0) oppure (reverse post-order). Un ordinamento valido esiste .
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']
Usare per build systems, task scheduling, prerequisiti dei corsi e dependency resolution. Se il risultato è più corto di V, il grafo ha un ciclo (nessun ordinamento valido). L'ordinamento in genere non è unico.
L'ordinamento delle dipendenze è ovunque — compiler, package manager, ricalcolo dei fogli di calcolo, pipeline CI.
Topological sort funziona anche come cycle detection per i grafi diretti.
Riconoscere un problema come "ordinare sotto vincoli" e ricorrere a topo sort è un forte segnale di seniority.