Topological sort sorteert lineair de vertices van een DAG (directed acyclic graph) zodat elk edge u->v u voor v heeft. Het beantwoordt de vraag "in welke volgorde kan ik deze taken doen gegeven hun afhankelijkheden?"
Twee veel voorkomende benaderingen: (herhaaldelijk knopen met in-degree 0 verwijderen) of (reverse post-order). Een geldige ordening bestaat .
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']
Gebruik voor build systems, taakplanning, cursusvoorwaarden en afhankelijkheidsoplossing. Als het resultaat korter is dan V, heeft de graaf een cyclus (geen geldige volgorde). De ordening is over het algemeen niet uniek.
Afhankelijkheidsordening komt overal voor — compilers, package managers, spreadsheet recalculation, CI pipelines.
Topological sort fungeert ook als cyclus detectie voor gerichte grafieken.
Een probleem herkennen als "bestelling onder beperkingen" en naar topo sort grijpen is een sterk senior signaal.