Topologisches Sortieren (Algorithmus 4.5)

So geht’s: Beim Öffnen läuft der Testclient mit den Fächern aus jobs.txt. Zuerst baut SymbolDigraph aus den Namen den Digraphen, die Tabelle rechts zeigt die Nummer jedes Fachs. Dann kommt Phase 1, die Zyklussuche: Orange ist der laufende dfs-Aufruf, orange gestrichelt sind die Knoten auf dem Rekursionspfad (onStack), blau ist die Kante, die gerade geprüft wird. Danach folgt Phase 2, die Tiefensuche für die Ordnung: Jeder Knoten, der fertig wird, wandert oben auf den Stapel reversePost. Am Ende liest man ihn von oben ab, das ist die topologische Ordnung. Am Graphen steht dann der Platz jedes Fachs, und die Probe zeigt, dass alle Kanten nach vorn zeigen. „mit Zyklus“ hängt die Zeile Theoretical CS/Introduction to CS an. Damit entsteht ein Kreis, die Zyklussuche findet ihn und färbt ihn rot, und es gibt keine Ordnung. „Zufalls-DAG“ und „Zufallsgraph“ erzeugen neue Beispiele, „↺ Neu starten“ springt zurück zu jobs.txt.

Erklärung

Topologisches Sortieren (Algorithmus 4.5), Klasse Topological.

Das Problem: Ablaufplanung mit Vorrangbedingungen. Aufgaben mit Abhängigkeiten, z. B. Studienfächer: Analysis vor Linearer Algebra, Einführung Informatik vor Algorithmen, Algorithmen vor Theoretischer Informatik. Gesucht ist eine Reihenfolge, in der jede Aufgabe erst nach allen ihren Voraussetzungen kommt. Als Digraph: Kante v→w heißt „v vor w“. Topologische Ordnung = alle Kanten zeigen nach vorn.

Voraussetzung: kein Zyklus. Wenn A vor B, B vor C und C vor A verlangt ist, gibt es keine Lösung. Der Graph muss ein DAG sein (directed acyclic graph, gerichtet azyklisch).

Der Code ist kurz, weil er sich auf zwei Hilfsklassen stützt:

• DirectedCycle: prüft per Tiefensuche, ob ein Zyklus existiert. Trick: Zusätzlich zu marked[] ein Array onStack[] für die Knoten, die gerade im aktuellen Rekursionspfad liegen. Trifft die Suche auf einen Knoten, der noch auf dem Pfad ist, ist ein Zyklus gefunden.
• DepthFirstOrder: normale Tiefensuche, merkt sich aber, in welcher Reihenfolge Knoten fertig werden (Postorder). Diese Reihenfolge wird auf einen Stapel [15] gelegt, beim Auslesen kommt sie umgekehrt heraus: reversePost().
• Topological: Zyklus vorhanden → order bleibt null, kein DAG. Sonst order = reversePost().
• isDAG(): order != null.

Satz F: Die umgekehrte Postorder-Reihenfolge eines DAG ist eine topologische Sortierung.

Beweis (für jede Kante v→w): Wenn dfs(v) die Kante prüft, gibt es drei Fälle:

• dfs(w) war schon aufgerufen und ist fertig → w ist vor v fertig.
• dfs(w) wurde noch nicht aufgerufen → wird jetzt aufgerufen und endet, bevor v endet.
• dfs(w) wurde aufgerufen, ist aber noch nicht fertig → dann gäbe es einen Pfad w→…→v, zusammen mit v→w ein Zyklus. Im DAG unmöglich.
• In allen möglichen Fällen wird w vor v fertig. Umgedreht steht also v vor w, genau wie verlangt.

Testclient: SymbolDigraph übersetzt Namen (Fächer aus jobs.txt) in Knotennummern und zurück, damit Klartext statt Zahlen ausgegeben wird. Trennzeichen wird mitgegeben, weil Fachnamen Leerzeichen enthalten.

Kosten: Zyklusprüfung plus eine Tiefensuche, insgesamt proportional zu V + E.

Typische Anwendungen: Kursplanung, Build-Systeme (welche Datei zuerst kompilieren), Paketmanager (Abhängigkeiten installieren), Tabellenkalkulation (Zellen in Abhängigkeitsreihenfolge berechnen).

Stand Kapitel 4:

• Algorithmus 4.1: Tiefensuche für Pfade [30]
• Algorithmus 4.2: Breitensuche für kürzeste Pfade [31]
• Algorithmus 4.3: Zusammenhangskomponenten [32]
• Algorithmus 4.4: Erreichbarkeit in Digraphen [33]
• Algorithmus 4.5: Topologisches Sortieren [34]