Topologische Sortierung

Pseudocode

Zwei Standardformulierungen, beide linear. Kahn arbeitet vorwärts von Knoten ohne Voraussetzungen; die DFS-Variante arbeitet rückwärts über die Abschlusszeiten.

// Kahn: entferne wiederholt einen Knoten ohne Eingangskanten
berechne eingangsgrad[v] für jeden Knoten
schlange = alle Knoten mit eingangsgrad 0
ordnung = []

solange die Schlange nicht leer ist:
    u = schlange.entnehmen()
    ordnung.anhängen(u)
    für jede Kante (u, v):
        eingangsgrad[v] -= 1
        wenn eingangsgrad[v] == 0: schlange.einfügen(v)

wenn ordnung.länge < V: der Graph hat einen Zyklus

// DFS-Variante: Umkehrung der Abschlussreihenfolge
führe DFS aus; lege jeden Knoten beim Abschluss auf einen Stapel
der abgeräumte Stapel ist eine gültige topologische Ordnung

Kahn hat einen praktischen Vorteil, den man kennen sollte: da er einen Zyklus daran erkennt, wie viele Knoten er ausgeben konnte, sind die übrig gebliebenen Knoten genau jene, die in einem Zyklus liegen oder ihm nachgelagert sind. Das macht ihn weit nützlicher als einen Wahrheitswert, wenn du melden musst, welche Abhängigkeiten zirkulär sind.

Durchgerechnetes Beispiel, Schritt für Schritt

Führe Kahn auf einem kleinen Build-Abhängigkeitsgraphen aus, in dem eine Kante X nach Y bedeutet, dass X vor Y gebaut werden muss.

Beispielgraph: Gerichtete Kanten A nach C, B nach C, C nach D und B nach D.

1. Eingangsgrade berechnen. A hat 0, B hat 0, C hat 2 (von A und B), D hat 2 (von C und B). Die Schlange beginnt mit A und B.
2. A ausgeben. Die Ordnung ist [A]. Verringere C auf Eingangsgrad 1. Noch nicht null, also wird C nicht eingereiht.
3. B ausgeben. Die Ordnung ist [A, B]. Verringere C auf 0, also wird C eingereiht. Verringere D auf 1.
4. C ausgeben. Die Ordnung ist [A, B, C]. Verringere D auf 0, also wird D eingereiht.
5. D ausgeben. Die Ordnung ist [A, B, C, D]. Die Schlange ist leer und alle vier Knoten wurden ausgegeben, es gibt also keinen Zyklus.

Eine gültige Ordnung ist A, B, C, D. Beachte, dass B, A, C, D genauso gültig ist: A und B haben keine Voraussetzungen und ihre relative Reihenfolge ist unbestimmt. Die topologische Ordnung ist nur eindeutig, wenn der Graph eine einzige Kette bildet, weshalb Tests prüfen sollten, ob jede Kante vorwärts zeigt, statt gegen eine erwartete Sequenz zu vergleichen.

Komplexität und woher sie kommt

Zeit: O(V + E) · Speicher: O(V)

Alle Eingangsgrade zu berechnen erfordert einen Durchlauf über alle Kanten, O(E). Jeder Knoten wird genau einmal eingereiht und entnommen, O(V). Jede Kante wird genau einmal betrachtet, nämlich wenn ihre Quelle ausgegeben und der Eingangsgrad des Ziels verringert wird, nochmals O(E). Der Speicher hält das Eingangsgradfeld, die Schlange und die Ausgabeliste, alle O(V). Die DFS-Variante hat dieselben Schranken, mit dem Rekursionsstapel anstelle der Schlange. Keine lässt sich verbessern, da jeder korrekte Algorithmus alle Kanten lesen muss, um die Einschränkungen zu kennen.

Wann Topologische Sortierung passt und wann nicht

Kahn und DFS liefern gleichermaßen gültige Ordnungen. Wähle danach, was du neben der Ordnung noch brauchst.

Häufige Fehler

• Ihn auf einem Graphen mit Zyklus ausführen und es nicht merken. Ein zyklischer Graph hat überhaupt keine topologische Ordnung. Kahn gibt stillschweigend eine Teilordnung aus, sofern du die Länge der Ausgabe nicht mit V vergleichst. Diese Prüfung ist der Zyklustest, und sie zu überspringen liefert eine plausible, aber unvollständige Build-Reihenfolge.
• Eine eindeutige Antwort erwarten. Zwei beliebige Knoten ohne Weg zwischen ihnen können in beliebiger Reihenfolge erscheinen. Ein Vergleich gegen eine fest verdrahtete Sequenz lässt Tests bei korrekten Implementierungen scheitern; prüfe stattdessen, dass jede Kante in der Ausgabe vorwärts zeigt.
• Die Kantenrichtung verwechseln. Bedeutet eine Kante X nach Y "X hängt von Y ab", so ist die topologische Ordnung genau umgekehrt zu dem, was du willst. Kläre die Konvention einmal an der Stelle, an der der Graph aufgebaut wird, statt die Ausgabe umzudrehen und zu hoffen.
• Ihn auf ungerichtete Graphen anwenden. Die topologische Ordnung ist nur für gerichtete azyklische Graphen definiert. Eine ungerichtete Kante ist ein Zweierzyklus, also hat kein ungerichteter Graph mit irgendeiner Kante eine topologische Ordnung.
• Zu tiefe Rekursion in der DFS-Variante. Eine Abhängigkeitskette aus Zehntausenden Knoten lässt den Aufrufstapel überlaufen. Kahn ist iterativ und kennt diese Grenze nicht, was ein Grund dafür ist, dass Build-Werkzeuge ihn bevorzugen.

Häufig gestellte Fragen

Wofür wird die topologische Sortierung verwendet?

Sie ordnet die Knoten eines gerichteten azyklischen Graphen so, dass jede Kante vorwärts zeigt, und beantwortet damit die Frage, in welcher Reihenfolge Aufgaben angesichts ihrer Abhängigkeiten laufen können. Sie plant Build-Systeme wie Make und Gradle, löst die Reihenfolge der Paketinstallation, ordnet Studienfächer mit Voraussetzungen, sortiert die Auswertung von Tabellenzellen und plant die Befehlsausführung in Compilern.

Was ist der Unterschied zwischen Kahn und dem DFS-Ansatz?

Kahn entfernt wiederholt Knoten mit Eingangsgrad null mithilfe einer Warteschlange und arbeitet vorwärts von dem, was keine Voraussetzungen hat. Der DFS-Ansatz führt eine Tiefensuche aus und gibt die Knoten in umgekehrter Abschlussreihenfolge aus. Beide sind O(V + E) und beide liefern gültige Ordnungen. Kahn ist iterativ und meldet, welche Knoten in Zyklen liegen; DFS ist kürzer, aber rekursiv.

Kann ein Graph mehr als eine topologische Ordnung haben?

Fast immer. Zwei beliebige Knoten ohne gerichteten Weg zwischen ihnen dürfen in beliebiger Reihenfolge erscheinen, sodass ein Graph mit V Knoten und wenigen Kanten sehr viele gültige Ordnungen haben kann. Eindeutig ist die Ordnung nur, wenn der Graph einen Hamiltonweg enthält, was für einen DAG eine einzige Kette durch alle Knoten bedeutet.

Wie erkennt man während der topologischen Sortierung einen Zyklus?

Bei Kahn zählst du die ausgegebenen Knoten: Kommen weniger als V heraus, liegen die übrigen in einem Zyklus oder ihm nachgelagert, denn keiner erreichte je den Eingangsgrad null. Bei der DFS-Variante beweist eine Rückkante zu einem Knoten, der noch im Rekursionsstapel liegt, einen Zyklus.

Wie ist die Zeitkomplexität der topologischen Sortierung?

O(V + E) Zeit und O(V) Speicher, sowohl für Kahn als auch für die DFS-Variante. Jeder Knoten wird einmal verarbeitet und jede Kante einmal betrachtet. Das ist optimal, da jeder Algorithmus mindestens alle Abhängigkeitskanten lesen muss.