Topologische Sortierung Rechner

Topologische Sortierung Rechner

Der Topologische Sortierung Rechner berechnet eine lineare Anordnung der Knoten eines gerichteten azyklischen Graphen (DAG), sodass jede gerichtete Kante von u nach v den Knoten u vor v platziert. Geben Sie Ihren Graphen als Kantenliste oder Adjazenzliste ein und das Tool liefert die topologische Ordnung mittels Kahn-Algorithmus oder DFS Post-Order, erkennt Zyklen (mit exaktem Zykluspfad), gruppiert Aufgaben in parallele Ausführungsschichten, zählt die Anzahl gültiger Sortierungen und animiert jeden Schritt auf einem interaktiven Graphen.

Was ist eine topologische Sortierung?

Gegeben sei ein gerichteter Graph G = (V, E). Eine topologische Sortierung (oder topologische Ordnung) ist eine lineare Anordnung v₁, v₂, …, vₙ seiner Knoten, sodass für jede gerichtete Kante (u → v) u vor v in der Anordnung erscheint. Eine topologische Ordnung existiert genau dann, wenn der Graph keine gerichteten Zyklen hat — das heißt, wenn der Graph ein DAG ist. Die Sortierung ist selten eindeutig: Ein Graph kann viele gültige topologische Sortierungen haben, wenn mehrere Knoten gleichzeitig den Eingangsgrad Null aufweisen.

Vom Rechner verwendete Algorithmen

Kahn-Algorithmus (BFS-basiert, 1962)

Der Kahn-Algorithmus ist die intuitivste topologische Sortierung. In jedem Schritt wählt er einen Knoten mit Eingangsgrad Null (keine eingehenden Kanten), fügt ihn der Ausgabe hinzu und "entfernt" ihn aus dem Graphen, indem er den Eingangsgrad jedes seiner Nachfolger verringert. Wenn mehrere Knoten den Eingangsgrad Null haben, kann zur Entscheidung ein Min-Heap (für die lexikographisch kleinste Ordnung) oder eine FIFO-Warteschlange (für die Einfügereihenfolge) verwendet werden. Der Kahn-Algorithmus läuft in O(|V| + |E|) Zeit und dient gleichzeitig als Zyklusdetektor: Wenn nach dem Leeren der Warteschlange noch ein Knoten einen Eingangsgrad > 0 hat, enthält der Graph einen Zyklus.

DFS Post-Order (Tarjan, 1976)

Der DFS-Algorithmus führt eine Tiefensuche (Depth-First Search) durch. Sobald ein Knoten abgeschlossen ist (d. h. alle seine Nachfolger wurden vollständig exploriert), wird er auf einen Stack gelegt. Das Umkehren des Stacks am Ende ergibt eine gültige topologische Ordnung. Die Zyklenerkennung erfolgt natürlich: Das Antreffen eines Knotens, der noch in Bearbeitung ist (markiert als GRAU), bedeutet, dass eine Rückwärtskante gefunden wurde und der Graph somit kein DAG ist. DFS Post-Order läuft ebenfalls in O(|V| + |E|) Zeit.

Parallele Ausführungsschichten

Eine geschichtete Ansicht eines DAG unterteilt seine Knoten in Ebenen, sodass jede Kante von einer niedrigeren Ebene zu einer höheren führt. Knoten in derselben Schicht sind voneinander unabhängig und können daher parallel verarbeitet werden. Die Anzahl der Schichten entspricht der Länge des längsten Pfades plus eins — dies ist der kritische Pfad des DAG, die minimale Anzahl an sequenziellen Runden, die benötigt werden, um alle Aufgaben auch bei unbegrenzter Parallelität abzuschließen. Dieser Rechner erstellt die Schichtenansicht automatisch, wenn die Eingabe ein DAG ist.

Zyklenerkennung

Wenn der Graph einen gerichteten Zyklus enthält, ist keine topologische Sortierung möglich. Unser Rechner gibt den exakten Zykluspfad aus (z. B. A → B → C → A) und markiert die Zykluskanten in der Visualisierung rot. Das Entfernen einer einzigen Kante im Zyklus reicht aus, um die Azyklizität wiederherzustellen.

Eingabeformate

Kantenliste

Schreiben Sie jede gerichtete Kante als Quelle -> Ziel, getrennt durch Kommas oder Zeilenumbrüche. Akzeptierte Pfeilvarianten: ->, →, =>, -->, :. Sie können Kanten auch verketten: A -> B -> C ist eine Kurzform für A->B und B->C. Knotenbezeichnungen können Buchstaben, Ziffern, Unterstriche, Bindestriche und Punkte enthalten.

Adjazenzliste

Schreiben Sie jeden Knoten, einen Doppelpunkt und seine direkten Nachfolger (Knoten, auf die er zeigt). Ein Knoten ohne Nachfolger benötigt dennoch eine Zeile, wie z. B. D:.

Bedienung des Rechners

1. Format wählen: Schalten Sie mit den Radio-Buttons zwischen Kantenliste und Adjazenzliste um.
2. Graph eingeben: Fügen Sie Ihre Daten ein oder klicken Sie auf eines der Schnellbeispiele (Anziehreihenfolge, Kursvoraussetzungen, Build-Ziele, Graph mit Zyklus usw.).
3. Algorithmus wählen: Kahns lexikographisch für eine eindeutige Ordnung; Einfügereihenfolge, um die Eingabereihenfolge zu bewahren; DFS Post-Order für die klassische Methode; oder Alle anzeigen, um alle Sortierungen nebeneinander zu sehen.
4. Klicken Sie auf "Topologisch sortieren": Die Sortierung, Zyklenerkennung, Schichtenansicht, kritische Pfadlänge, Gesamtzahl der gültigen Sortierungen und ein interaktiver Graph erscheinen unten.
5. Erkunden: Drücken Sie Play, um zuzusehen, wie jeder Knoten Schritt für Schritt ausgegeben wird. Die Eingangsgrad-Badges werden live aktualisiert. Ziehen Sie Knoten, um das Layout anzupassen.

Anwendungen in der Praxis

Build-Systeme und Compiler

Werkzeuge wie make, Bazel, Gradle und npm sortieren ihre Build-Ziele topologisch, sodass jedes Ziel erst kompiliert wird, nachdem alle seine Abhängigkeiten fertig sind. Ein Zyklus im Abhängigkeitsgraph wird meist als fataler Fehler gemeldet — das Build-System kann nicht entscheiden, wo es anfangen soll.

Aufgabenplanung

Projektmanager verwenden DAGs, um Aufgabenabhängigkeiten zu erfassen. Die topologische Sortierung ergibt eine gültige Ausführungsreihenfolge, und die Schichtenansicht zeigt die minimale Rundenzahl bei unbegrenzter Parallelität. Die längste Kette ist der kritische Pfad, der die Projektdauer bestimmt.

Kursplanung

Ein Kurskatalog an der Universität ist ein DAG: Kanten stellen Voraussetzungen dar. Eine topologische Ordnung ist ein gültiger Studienplan, und die Schichten zeigen den Studenten, welche Kurse sie in jedem Semester parallel belegen können.

Tabellenkalkulation

Wenn sich eine Zelle ändert, muss eine Tabellenkalkulation jede nachgelagerte Zelle in der Reihenfolge ihrer Abhängigkeiten neu berechnen — eine topologische Sortierung des Zell-Abhängigkeits-DAG. Zirkelbezüge (Zyklen) werden von der Anwendung abgelehnt.

Paketmanager und Plugin-Loader

Apt, pip, Homebrew, Maven und unzählige Plugin-Frameworks lösen die Installations- oder Ladereihenfolge durch topologisches Sortieren ihrer Abhängigkeits-DAGs.

Symbolauflösung und Instruktions-Scheduling

Compiler verwenden topologische Sortierung, um Deklarationen zu ordnen, und CPUs nutzen Datenabhängigkeits-DAGs, um Instruktionen im Reorder-Buffer zu planen, ohne Datenkonflikte zu verursachen.

Zählen topologischer Sortierungen

Für einen DAG mit n Knoten kann die Anzahl der verschiedenen gültigen topologischen Sortierungen von 1 (bei einer total geordneten Kette) bis n! (bei einem kantenlosen Graphen) reichen. Die Berechnung der exakten Anzahl ist im Allgemeinen #P-vollständig. Für Graphen mit bis zu 16 Knoten ermittelt dieser Rechner sie jedoch mittels Bitmask-Dynamischer-Programmierung: f(S) = Σ f(S ∪ {v}) über alle v ∉ S, deren Vorgänger alle in S liegen.

Komplexität und Performance

• Zeit: Sowohl der Kahn-Algorithmus als auch DFS Post-Order laufen in O(|V| + |E|) — linear zur Größe des Graphen.
• Platz: O(|V|) für die Verfolgung der Eingangsgrade und die Ausgabereihenfolge, plus O(|V| + |E|) für die Adjazenzstruktur.
• Zyklenerkennung: In beide Algorithmen integriert. Kahn erkennt Zyklen, wenn |Ausgabe| < |V|; DFS erkennt sie, wenn eine Rückwärtskante (GRAUER Nachbar) gefunden wird.
• Limits im Tool: Bis zu 80 Knoten und 800 Kanten für die interaktive Visualisierung. Das Zählen von Sortierungen ist auf 16 Knoten begrenzt.

Häufig gestellte Fragen

Was ist eine topologische Sortierung?

Eine topologische Sortierung eines gerichteten azyklischen Graphen ist eine lineare Anordnung seiner Knoten, bei der für jede gerichtete Kante von u nach v der Knoten u vor v steht. Sie stellt eine gültige Reihenfolge zur Bearbeitung von Aufgaben unter Berücksichtigung ihrer Abhängigkeiten dar.

Welchen Algorithmus verwendet dieser Rechner?

Der Rechner führt sowohl den Kahn-Algorithmus als auch DFS Post-Order aus. Der Kahn-Algorithmus entfernt wiederholt Knoten mit Eingangsgrad Null. DFS Post-Order nutzt die Tiefensuche und kehrt die Abschlussreihenfolge um. Beide benötigen O(|V| + |E|) Zeit.

Was passiert, wenn mein Graph einen Zyklus hat?

Ein Graph mit einem gerichteten Zyklus hat keine topologische Sortierung. Der Rechner erkennt dies, markiert den Zyklus in der Visualisierung rot und gibt den Pfad aus, damit Sie wissen, welche Kanten zur Korrektur entfernt werden müssen.

Was ist die lexikographisch kleinste topologische Ordnung?

Wenn mehrere Sortierungen möglich sind, ist die lexikographisch kleinste jene, bei der in jedem Schritt der alphabetisch kleinste verfügbare Knoten (Eingangsgrad 0) gewählt wird. Dies ist der Standardmodus bei Kahn in diesem Rechner.

Was ist die Schichten- oder Ebenenansicht?

Sie gruppiert Knoten nach ihrer maximalen Entfernung von einer Quelle. Knoten in einer Schicht können parallel verarbeitet werden. Die Anzahl der Schichten gibt die minimale Anzahl an Runden für das gesamte Projekt an.

Kann ein Graph viele gültige topologische Sortierungen haben?

Ja. Sobald der Kahn-Algorithmus mehr als einen Knoten mit Eingangsgrad Null zur Auswahl hat, führt jede Wahl zu einer anderen gültigen Sortierung. Dieser Rechner zählt diese Möglichkeiten für bis zu 16 Knoten exakt.

Was ist der Unterschied zwischen Kahn und DFS Post-Order?

Kahn arbeitet Top-down: Er wählt Quellen zuerst. DFS Post-Order arbeitet Bottom-up: Er schließt Senken zuerst ab und stellt sie ans Ende der Sortierung. Beider Komplexität ist O(|V| + |E|), aber sie erzeugen oft unterschiedliche (dennoch gültige) Ergebnisse.

Wie groß darf der Graph maximal sein?

Das Tool unterstützt bis zu 80 Knoten und 800 Kanten. Das Zählen der Sortierungen ist auf 16 Knoten beschränkt, da das Problem #P-vollständig ist und der Zustandsraum exponentiell (2ⁿ) wächst.

Weiterführende Literatur

• Topologische Sortierung — Wikipedia
• Gerichteter azyklischer Graph — Wikipedia
• Tiefensuche — Wikipedia
• Methode des kritischen Pfades — Wikipedia
• Starke Zusammenhangskomponente — Wikipedia