Topologische Sortierung

Kurz: Eine topologische Sortierung ordnet die Knoten eines gerichteten Graphen ohne Zyklus so an, dass jeder Knoten vor allen Knoten kommt, auf die er zeigt.

Genauer: Sie beantwortet die Frage „In welcher Reihenfolge muss ich Aufgaben erledigen, wenn manche vor anderen fertig sein müssen?”. Gibt es einen Zyklus, existiert keine gültige Reihenfolge.

Im Detail

• Kahn-Algorithmus: Wiederholt Knoten ohne eingehende Kanten entnehmen und ihre ausgehenden Kanten entfernen.
• DFS-Variante: Tiefensuche, Knoten nach dem vollständigen Besuch aller Nachfolger auf einen Stapel legen, am Ende umdrehen.
• Zyklus-Erkennung: Bleiben Knoten übrig, gibt es einen Zyklus (zum Beispiel zyklische Abhängigkeit).
• Einsatz: Build-Systeme, Paketmanager (Abhängigkeiten), Kursplanung, Tabellen-Neuberechnung.
• Laufzeit: O(Knoten + Kanten).

Siehe auch: Graph (Datenstruktur)