Topologische Sortierung: Abhängigkeiten in gerichteten Graphen in eine Reihenfolge bringen

Topologische Sortierung ordnet die Knoten eines gerichteten azyklischen Graphen (DAG) so an, dass jede Kante von einem früheren zu einem späteren Knoten zeigt. Ist eine Kante A → B vorhanden, steht A in der sortierten Reihenfolge garantiert vor B. Eine topologische Sortierung existiert genau dann, wenn der Graph keine Zyklen enthält.

Wofür man sie braucht

Überall dort, wo Aufgaben von anderen Aufgaben abhängen, liefert die topologische Sortierung eine gültige Bearbeitungsreihenfolge:

• Build-Systeme wie Make oder Gradle ermitteln, in welcher Reihenfolge Quelldateien übersetzt und Pakete gepackt werden müssen.
• Paketmanager nutzen sie, um Abhängigkeiten (Bibliotheken, Module) vor ihren Nutzern zu installieren.
• Task-Scheduler und Workflow-Engines planen Jobs, deren Ausführung von anderen Jobs abhängt.
• Kursplanung: Ist ein Kurs Voraussetzung für einen anderen, gibt die Sortierung die sinnvolle Semesterfolge vor.

Kahn-Algorithmus

1. Grad (Anzahl eingehender Kanten) für jeden Knoten berechnen
2. Alle Knoten mit Grad 0 in eine Warteschlange
3. Solange die Warteschlange nicht leer ist:
   a. Knoten v entnehmen und ausgeben
   b. Für jede ausgehende Kante v → w: Grad von w verringern
   c. Wird der Grad von w dadurch 0, kommt w in die Warteschlange
4. Wurden weniger Knoten ausgegeben als vorhanden,
   enthält der Graph einen Zyklus

Der Kahn-Algorithmus arbeitet iterativ mit einer Queue und benötigt eine Adjazenzliste der ausgehenden Kanten. Alternativ lässt sich die Sortierung mit einer Tiefensuche und Rekursion erzeugen: Knoten werden in der Reihenfolge ihres Abschlusses gesammelt und am Ende umgekehrt ausgegeben. Beide Varianten laufen in O(V + E) bei V Knoten und E Kanten.

Praxis-Tipps

• Ein Zyklus (z.B. gegenseitige Abhängigkeit zweier Module) macht die Sortierung unmöglich — der Kahn-Algorithmus erkennt ihn zuverlässig, weil dann Knoten mit Grad > 0 übrig bleiben.
• Ist die Reihenfolge nicht eindeutig, kann man Knoten mit Grad 0 in beliebiger Reihenfolge abarbeiten — z.B. lexikografisch oder nach Priorität.
• Die topologische Sortierung ist eine Spezialform der Traversierung: Sie besucht jeden Knoten genau einmal, respektiert aber zusätzlich die Kantenrichtung.

Verwandte Grundlagen: Graph-Datenstruktur, Algorithmus, Rekursion.