Topologisches Sortieren ordnet die Knoten eines DAG (gerichteter azyklischer Graph) linear an, sodass jede Kante u->v u vor v hat. Es beantwortet die Frage: "In welcher Reihenfolge kann ich diese Aufgaben bei ihren Abhängigkeiten ausführen?"
Zwei häufige Ansätze: (wiederholt Knoten mit In-Grad 0 entfernen) oder (umgekehrte Post-Order). Eine gültige Ordnung existiert .
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']
Verwenden Sie es für Build-Systeme, Task-Scheduling, Kursvoraussetzungen und Dependency-Auflösung. Wenn das Ergebnis kürzer als V ist, hat der Graph einen Zyklus (keine gültige Ordnung). Die Ordnung ist generell nicht eindeutig.
Abhängigkeitsordnung ist überall vorhanden — Compiler, Package Manager, Tabellenkalkulationen-Neuberechnung, CI-Pipelines.
Topologisches Sortieren funktioniert auch als Zyklenerkennung für gerichtete Graphen.
Ein Problem als "Ordnung unter Einschränkungen" zu erkennen und topologisches Sortieren einzusetzen ist ein starkes Senior-Signal.