Rechner für topologische Sortierung
DAG · Kahn-Algorithmus · Tiefensuche · Zykluserkennung · alle Reihenfolgen
Finden Sie eine gültige lineare Reihenfolge eines gerichteten azyklischen Graphen (DAG). Unterstützt werden der Kahn-Algorithmus mit Breitensuche und die Tiefensuche; Zyklen werden erkannt und für kleine Graphen alle gültigen Reihenfolgen aufgezählt.
Schnellbeispiele
Akzeptierte Formate: A→B A->B A-B A,B durch Kommas oder Zeilenumbrüche getrennt.
Klicken Sie auf eine Zelle, um eine Kante vom Zeilen- zum Spaltenknoten hinzuzufügen oder zu entfernen.
Zyklus erkannt – topologische Sortierung unmöglich
Eine topologische Reihenfolge existiert nur für gerichtete azyklische Graphen (DAGs). Dieser Graph enthält einen Zyklus; daher gibt es keine gültige Reihenfolge.
Topologische Reihenfolge (Kahn-Algorithmus)
DAG-Visualisierung
Die Knoten sind nach ihrer topologischen Position von hell- bis dunkelgrün gefärbt. Zahlen zeigen die Position in der Reihenfolge.
Schrittweiser Ablauf – Kahn-Algorithmus
In jedem Schritt wird ein Knoten mit Eingangsgrad 0 entnommen, dem Ergebnis hinzugefügt und der Eingangsgrad seiner Nachbarn verringert.
| Schritt | Entnommen | Warteschlange danach | Eingangsgrade (geändert) | Bisheriges Ergebnis |
|---|
Abschlusszeiten der Tiefensuche
Nach absteigender Abschlusszeit der Tiefensuche sortierte Knoten ergeben die topologische Reihenfolge.
| Knoten | Entdeckungszeit | Abschlusszeit | Topologische Position |
|---|
Alle gültigen topologischen Reihenfolgen
Unten sind alle gültigen topologischen Reihenfolgen aufgeführt. Jede davon ist eine korrekte Lösung.
Was ist eine topologische Sortierung?
Topologische Sortierung oder topologische Reihenfolge bezeichnet eine lineare Anordnung der Knoten eines gerichteten azyklischen Graphen (DAG). Für jede gerichtete Kante u → v muss u vor v stehen. Anders als beim üblichen Sortieren geht es um die Reihenfolge von Abhängigkeiten, nicht um Zahlen oder Buchstaben.
Eine topologische Sortierung existiert nur, wenn der Graph keine gerichteten Zyklen enthält. Bei A → B → C → A müsste A vor B, B vor C und zugleich C vor A stehen – das ist unmöglich.
Gerichtete azyklische Graphen (DAGs)
Ein gerichteter azyklischer Graph (DAG) ist ein Graph, dessen Kanten eine Richtung besitzen und der keine gerichteten Zyklen enthält. DAGs entstehen überall dort, wo Abhängigkeiten modelliert werden: Aufgabe A muss abgeschlossen sein, bevor Aufgabe B beginnt. Die Kanten stehen für „muss vorher kommen“.
Typische Beispiele sind Kursvoraussetzungen, Abhängigkeiten beim Erstellen von Software, die Reihenfolge von Rezeptschritten und Tabellenkalkulationsformeln, bei denen D1 = A1 + B1 vor E1 = D1 · 2 berechnet werden muss.
Kahn-Algorithmus (Breitensuche)
Der 1962 von Arthur B. Kahn veröffentlichte Algorithmus ist besonders anschaulich. Er entfernt wiederholt Knoten ohne verbleibende Abhängigkeiten:
- Eingangsgrad berechnen: Für jeden Knoten wird die Zahl eingehender Kanten bestimmt.
- Warteschlange initialisieren: Alle Knoten mit Eingangsgrad 0 werden eingefügt.
- Solange die Warteschlange nicht leer ist: Knoten u entnehmen, an das Ergebnis anhängen und für jeden Nachbarn v den Eingangsgrad verringern. Wird er 0, kommt v in die Warteschlange.
- Zyklusprüfung: Enthält das Ergebnis alle Knoten, ist der Graph ein DAG. Andernfalls gehören die verbleibenden Knoten zu einem Zyklus.
Zeitkomplexität: O(V + E), wobei V die Anzahl der Knoten und E die Anzahl der Kanten bezeichnet. Das ist optimal, weil jeder Knoten und jede Kante mindestens einmal untersucht werden muss.
Topologische Sortierung mit Tiefensuche
Das Verfahren mit Tiefensuche speichert für jeden Knoten die Abschlusszeit, also den Zeitpunkt, an dem alle Nachfolger vollständig besucht sind. Knoten mit höherer Abschlusszeit stehen weiter vorn. Eine Rückkante zu einem Vorfahren im aktuellen Suchpfad – einem „grauen“ Knoten im Dreifarbschema – zeigt einen Zyklus an.
Kahn-Algorithmus und Tiefensuche haben beide die Komplexität O(V + E), können für denselben Graphen jedoch verschiedene gültige Reihenfolgen liefern.
Anwendungen der topologischen Sortierung
| Bereich | Anwendung | Bedeutung im DAG |
|---|---|---|
| Build-Systeme | GNU Make, Bazel, npm | Quelldatei A muss vor dem Binden von B übersetzt werden |
| Bildung | Kursplanung | Voraussetzungskurs muss zuerst belegt werden |
| Tabellenkalkulation | Neuberechnung von Formeln | Zelle muss vor abhängigen Zellen berechnet werden |
| Compiler | Befehlsplanung | Befehlsergebnis wird später benötigt |
| Paketverwaltungen | Apt, pip, npm install | Abhängigkeit muss vor abhängigen Paketen installiert werden |
| Projektplanung | Methode des kritischen Pfads | Aufgabe muss vor Beginn des Nachfolgers abgeschlossen sein |
Wie viele gültige Reihenfolgen gibt es?
Ein Graph kann mehrere gültige topologische Reihenfolgen haben. Für die Kette A → B → C → D gibt es genau eine. Beim „Diamanten“ A → B → D und A → C → D sind dagegen [A, B, C, D] und [A, C, B, D] gültig. Die Anzahl hängt von der Graphstruktur ab und wächst schnell; ihre Bestimmung ist ein #P-vollständiges Problem. Dieser Rechner zählt für kleine Graphen mit bis zu sieben Knoten alle Reihenfolgen auf.
Details zur Zykluserkennung
Beim Kahn-Algorithmus wird ein Zyklus erkannt, wenn das Ergebnis nach dem Leeren der Warteschlange weniger als V Knoten enthält. Die übrigen Knoten gehören zu Zyklen und besitzen jeweils mindestens eine eingehende Kante aus diesem Bereich; deshalb erreicht keiner Eingangsgrad 0. Bei der Tiefensuche signalisiert ein bereits „grauer“, noch in Bearbeitung befindlicher Knoten eine Rückkante und damit einen Zyklus.