Topological sort ordner lineært toppunktene i en DAG (directed acyclic graph) slik at hver kant u->v har u før v. Det svarer på "i hvilken rekkefølge kan jeg gjøre disse oppgavene gitt deres avhengigheter?"
To vanlige tilnærminger: (fjern gjentatte ganger noder med in-degree 0) eller (reverse post-order). En gyldig ordning finnes .
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']
Bruk for build systems, oppgaveplassering, kursforventninger og avhengighetsløsning. Hvis resultatet er kortere enn V, har grafen en syklus (ingen gyldig rekkefølge). Ordningen er generelt ikke unik.
Avhengighetsordning er overalt — compilers, package managers, spreadsheet recalculation, CI pipelines.
Topological sort fungerer også som syklusdeteksjon for rettede grafer.
Å gjenkjenne et problem som "ordning under begrensninger" og gripe til topo sort er et sterkt seniorsignal.