Topologisches Sortieren
Lesen anpassen
Nach dieser Lektion kannst du
eine topologische Ordnung an allen gerichteten Kanten prüfen,
Kahns Algorithmus mit Eingangsgraden und einer Warteschlange ausführen,
die Existenz einer Ordnung und die Zyklenerkennung begründen,
die DFS-Variante, die Laufzeit und die Grenzen einer solchen Reihenfolge erklären.
Vorausgesetzt: Graphen und Suche: Breitensuche und Tiefensuche
Ein Team erstellt Lernmaterial. Bevor Seiten gesetzt werden, müssen Inhalte gegliedert und Bilder geprüft sein. Aufgaben lassen sich dagegen teilweise schon prüfen, während die Seiten entstehen. Ein alphabetisch sortierter Arbeitsplan berücksichtigt solche Voraussetzungen nicht.
Gesucht ist eine Reihenfolge, in der niemand auf ein noch nicht erledigtes Arbeitspaket angewiesen ist. Möglicherweise sind mehrere Reihenfolgen richtig. Möglicherweise enthalten die Vorgaben aber auch einen Widerspruch: A wartet auf B, B wiederum auf A.
Du kennst gerichtete Graphen aus der Graphensuche. Hier bedeutet ein Pfeil ausdrücklich: Die Aufgabe am Anfang muss vor der Aufgabe am Ende fertig sein. Aus diesen örtlichen Bedingungen an einzelnen Pfeilen soll ein vollständiger Arbeitsplan entstehen.
Zwei Aufgaben A und B haben keine unerledigten Voraussetzungen. Muss ein korrekter Plan mit A beginnen?
Ein Arbeitsplan als gerichteter Graph
Ein Arbeitsplan als gerichteter Graph
Wir verwenden sieben erfundene Arbeitspakete. Die Tabelle nennt jeweils alle unmittelbaren Voraussetzungen. „Keine“ bedeutet hier wirklich: keine Kante führt in diesen Knoten hinein.
| Knoten | Arbeitspaket | Unmittelbare Voraussetzungen |
|---|---|---|
| A | Quellen sammeln | keine |
| B | Format festlegen | keine |
| C | Inhalte gliedern | A und B |
| D | Bilder prüfen | A |
| E | Seiten setzen | C und D |
| F | Aufgaben prüfen | B und C |
| G | Material veröffentlichen | E und F |
Damit gibt es neun Pfeile: A nach C, A nach D, B nach C, B nach F, C nach E, C nach F, D nach E, E nach G und F nach G. Zum Beispiel bedeutet C nach F: F darf erst beginnen, wenn C abgeschlossen ist. Die umgekehrte Lesart würde ein anderes Problem modellieren.
Die Folge A, B, D, C, E, F, G erfüllt alle neun Bedingungen. Auch B, A, C, D, F, E, G passt. D und C dürfen ihre Reihenfolge ändern, sobald ihre jeweiligen Voraussetzungen erfüllt sind.
Prüfe eine Kandidatenfolge Pfeil für Pfeil. Weder die Form einer Zeichnung noch die alphabetische Reihenfolge beweist, dass alle Abhängigkeiten eingehalten sind.
Topologische Ordnung und DAG
Sei ein endlicher gerichteter Graph. ist seine Knotenmenge, seine Kantenmenge. Eine topologische Ordnung ist eine Liste aller Knoten, in der jeder Knoten genau einmal vorkommt und bei jeder Kante der Knoten vor steht. Bezeichnet die Position von in der Liste, lautet die Bedingung für alle Kanten .
Ein gerichteter Zyklus ist ein geschlossener gerichteter Weg, der zu seinem Ausgangsknoten zurückführt; dazwischen werden die Knoten nicht wiederholt. Auch eine Schleife von einem Knoten zu sich selbst ist ein Zyklus. Ein gerichteter Graph ohne gerichteten Zyklus heißt gerichteter azyklischer Graph, kurz DAG nach der englischen Bezeichnung directed acyclic graph.
Das Wort „Sortieren“ meint hier also das Einhalten von Abhängigkeiten. Ein Zahlenvergleich ist nicht nötig. Für einen Graphen mit isolierten Knoten, also Knoten ohne ein- oder ausgehende Kanten, müssen diese ebenfalls in der Liste stehen. Für den leeren Graphen ist die leere Liste eine gültige Ordnung.
Eine vollständige Liste kann trotzdem falsch sein
Eine vollständige Liste kann trotzdem falsch sein
Die Liste A, C, B, D, E, F, G enthält alle sieben Knoten genau einmal. Sie ist trotzdem ungültig: Die Kante B nach C verlangt B vor C, in der Liste steht C aber davor.
Um eine Liste systematisch zu prüfen, trägst du zunächst die Position jedes Knotens ein. Prüfe dabei Vollständigkeit und doppelte Einträge. Danach vergleichst du für jede Kante die beiden Positionen. Sobald eine Kante rückwärts führt, ist die Liste keine topologische Ordnung.
Es genügt, die unmittelbaren Kanten zu prüfen. Besteht ein gerichteter Weg von u über v nach w, folgt aus „u vor v“ und „v vor w“ bereits „u vor w“. Zusätzliche Kanten für alle mittelbaren Voraussetzungen sind für diesen Test nicht nötig.
Eine gültige Ausgabe muss sowohl alle Knoten erfassen als auch jede Kantenbedingung erfüllen. Das sind zwei verschiedene Anforderungen.
Welche Folge erfüllt alle Abhängigkeiten des Arbeitsplans?
Eine Ordnung existiert genau für DAGs
Ein endlicher gerichteter Graph besitzt genau dann eine topologische Ordnung, wenn er keinen gerichteten Zyklus enthält.
Beweisidee: Ein Zyklus würde eine Aufgabe vor sich selbst verlangen. Ohne Zyklus lässt sich dagegen immer ein Knoten ohne noch offene Voraussetzung voranstellen.
Angenommen, es gibt eine topologische Ordnung und zugleich einen Zyklus von v₁ über v₂ und weitere Knoten zurück nach v₁. Entlang jeder Zykluskante müssten die Positionen streng steigen. Nach dem Umlauf wäre die Position von v₁ also kleiner als sie selbst. Das ist unmöglich. Eine Schleife würde unmittelbar dieselbe unmögliche Ungleichung verlangen.
Für die Gegenrichtung zeigen wir zuerst: Jeder nichtleere endliche DAG hat einen Knoten ohne eingehende Kante. Andernfalls könntest du bei einem beliebigen Knoten beginnen und immer einem eingehenden Pfeil zu einem Vorgänger folgen. Weil es nur endlich viele Knoten gibt, wiederholt sich irgendwann ein Knoten. Der entsprechende Abschnitt der Vorgängerkette bildet, in Pfeilrichtung gelesen, einen gerichteten Zyklus. Das widerspricht der Voraussetzung.
Nun folgt die Existenz durch Induktion über die Knotenzahl. Bei null Knoten genügt die leere Liste. Bei einem nichtleeren DAG wähle einen Knoten u ohne eingehende Kante und entferne ihn mit seinen ausgehenden Kanten. Der Rest ist weiterhin azyklisch und hat einen Knoten weniger. Nach Induktionsannahme besitzt er eine topologische Ordnung. Stelle u davor. Keine Kante verlangt einen Restknoten vor u; alle Kanten aus u führen nach hinten, und alle übrigen Kanten stimmen nach Induktionsannahme. Die entstandene Liste ist gültig.
Eingangsgrad im Restgraphen
Der Eingangsgrad eines Knotens ist die Zahl seiner eingehenden Kanten. Für unseren Algorithmus zählt der Restgraph: die noch nicht ausgegebenen Knoten mit den Kanten zwischen ihnen. Der aktuelle Eingangsgrad zählt deshalb nur noch unerledigte unmittelbare Voraussetzungen.
Im Ausgangsgraphen haben A und B Eingangsgrad 0, C hat 2, D hat 1, E und F haben jeweils 2 und G hat 2. Wird A ausgegeben, fallen seine beiden ausgehenden Kanten im Restgraphen weg. Der Eingangsgrad von C sinkt auf 1, der von D auf 0. C ist noch nicht bereit, weil B weiterhin fehlt.
Ein Knoten mit Eingangsgrad 0 heißt hier bereit. Seine ausgehenden Kanten stören nicht: Sie nennen Aufgaben, die erst später folgen sollen. Ein Knoten ohne ausgehende Kanten ist dagegen nicht automatisch bereit. G hat keine Nachfolger, wartet anfangs aber auf E und F.
Kahns Algorithmus entwickeln
Kahns Algorithmus entwickeln
Die Existenzbegründung lässt sich in ein Verfahren übersetzen. Eine Warteschlange hält die bereiten Knoten bereit; vorne wird entnommen, hinten werden neue Knoten angefügt.
Zähle zunächst für jeden Knoten alle eingehenden Kanten. Trage jeden Knoten mit Eingangsgrad 0 genau einmal in die Warteschlange ein.
Der vollständige Lauf mit einer FIFO-Warteschlange
Der vollständige Lauf mit einer FIFO-Warteschlange
FIFO bedeutet: first in, first out; wer zuerst eingetragen wird, wird zuerst entnommen. Anfangs tragen wir A vor B ein. Ausgehende Nachbarn werden alphabetisch durchgesehen. Neu bereite Knoten kommen hinten dazu; die gesamte Warteschlange wird dabei nicht erneut alphabetisch sortiert.
| Gerade ausgegeben | Änderung der Eingangsgrade | Warteschlange danach |
|---|---|---|
| noch keiner | A: 0, B: 0, C: 2, D: 1, E: 2, F: 2, G: 2 | A, B |
| A | C: 2 auf 1; D: 1 auf 0 | B, D |
| B | C: 1 auf 0; F: 2 auf 1 | D, C |
| D | E: 2 auf 1 | C |
| C | E: 1 auf 0; F: 1 auf 0 | E, F |
| E | G: 2 auf 1 | F |
| F | G: 1 auf 0 | G |
| G | keine ausgehende Kante | leer |
Die Ausgabe lautet A, B, D, C, E, F, G. Insbesondere steht D vor C, obwohl C alphabetisch davor läge. D war früher in die Warteschlange gekommen.
An jedem Schritt kannst du kontrollieren: Die gespeicherten Eingangsgrade gehören zum Restgraphen, nicht mehr zum ursprünglichen Graphen. Die Ausgabeliste wächst um genau einen Knoten pro Entnahme. Nach sieben Entnahmen ist sie vollständig.
Eine dokumentierte Auswahlregel macht den Lauf nachvollziehbar. Andere Regeln können andere, ebenfalls gültige Ordnungen liefern.
Probier es aus
Warum Kahn korrekt ist und Zyklen erkennt
Kahns Algorithmus gibt bei einem DAG eine topologische Ordnung aus. Bleiben nach dem Leeren der Warteschlange Knoten übrig, enthält der Graph einen gerichteten Zyklus.
Zu Beginn jeder Schleifenrunde gilt die folgende Invariante: Für jeden noch nicht ausgegebenen Knoten ist der gespeicherte Eingangsgrad gleich der Zahl seiner eingehenden Kanten aus dem Restgraphen. Die Warteschlange enthält genau die bereiten Restknoten.
Nach dem anfänglichen Zählen stimmt diese Aussage. Entfernen wir einen bereiten Knoten u, betrifft das genau seine ausgehenden Kanten. Für jede dieser Kanten verringert der Algorithmus den richtigen Zähler um 1. Wird ein Zähler 0, wird der betreffende Knoten eingetragen. Ein Knoten kann nur einmal von positiv auf 0 wechseln; die anfangs bereiten Knoten waren bereits einmal eingetragen. Die Invariante bleibt erhalten.
Bei der Ausgabe von u kann kein noch nicht ausgegebener Vorgänger von u existieren, sonst wäre der aktuelle Eingangsgrad positiv. Deshalb steht bei jeder Kante ihr Anfang vor ihrem Ende, sobald beide ausgegeben sind. Werden alle Knoten ausgegeben, ist die Liste somit eine topologische Ordnung.
Bleibt bei leerer Warteschlange ein nichtleerer Restgraph übrig, hat dort jeder Knoten positiven Eingangsgrad. Das Vorgängerargument aus dem Existenzbeweis liefert einen gerichteten Zyklus im Restgraphen. In einem DAG kann dieser Fall nicht auftreten: Solange Knoten übrig sind, ist mindestens einer bereit. Ein nichtleerer Rest beweist also eine widersprüchliche Abhängigkeit im Eingabegraphen.
Blockiert bedeutet nicht selbst Teil eines Zyklus
Blockiert bedeutet nicht selbst Teil eines Zyklus
Betrachte einen anderen Graphen: A nach B, B nach C, C nach A und C nach D. Dazu kommt ein isolierter Knoten E. Anfangs ist nur E bereit. Kahn gibt E aus; danach ist die Warteschlange leer, obwohl A, B, C und D noch übrig sind.
A, B und C bilden einen Zyklus. D liegt dagegen auf keinem Zyklus: Von D führt überhaupt keine Kante zurück. D bleibt trotzdem blockiert, weil seine Voraussetzung C nie freigegeben wird.
Die Teilausgabe E ist keine topologische Ordnung des ganzen Graphen. Sie beschreibt nur den ausführbaren Anfang. Die Zahl der ausgegebenen Knoten ist 1 statt 5. Für eine konkrete Erklärung des Fehlers kannst du zusätzlich einen Zyklus als Folge von Pfeilen suchen. Die Restknoten allein sind noch keine solche Zyklusfolge.
Zyklenerkennung und die Ausgabe eines konkreten Zyklus sind verschiedene Aufgaben. Aus dem Restgraphen lässt sich nicht schließen, dass jeder Restknoten selbst im Zyklus liegt.
Im gerade beschriebenen Restgraphen bleibt D übrig. Was folgt daraus?
DFS-Abschlussreihenfolge
Eine zweite Methode verwendet die Tiefensuche, kurz DFS. Ein Knoten ist weiß, solange er noch nicht besucht wurde, grau, solange sein rekursiver Aufruf noch aktiv ist, und schwarz, sobald alle seine ausgehenden Kanten bearbeitet sind. Die Farben sind Zustandsnamen; eine Umsetzung braucht keine farbige Zeichnung.
Beim Schwarzwerden hängst du den Knoten an eine Abschlussliste an. Starte nach dem Ende einer Suche bei einem weiteren weißen Knoten, bis alle Knoten besucht wurden. Diese vollständige Suche ist auch bei getrennten Teilen des Graphen nötig.
In einem DAG ist die umgekehrte Abschlussliste eine topologische Ordnung. Gemeint ist die Reihenfolge des Fertigwerdens, nicht die Reihenfolge des ersten Besuchs. Triffst du beim Bearbeiten einer gerichteten Kante auf einen grauen Knoten, meldest du einen Zyklus und verwirfst die Ausgabe als vollständigen Abhängigkeitsplan.
Warum die umgekehrten DFS-Abschlüsse passen
In einer vollständigen Tiefensuche eines DAGs wird für jede Kante von u nach v der Knoten v vor u abgeschlossen. Die umgekehrte Abschlussliste erfüllt deshalb alle Kantenbedingungen.
Betrachte den Zeitpunkt, an dem die Kante von u nach v bearbeitet wird. Ist v weiß, wird v rekursiv besucht und vollständig abgeschlossen, bevor die Suche bei u fortsetzt und später u abschließt. Ist v schwarz, wurde v bereits abgeschlossen, während u noch aktiv ist.
Ist v grau, gehört v zum aktiven Aufrufpfad der Suche. Dieser enthält einen gerichteten Weg von v nach u. Zusammen mit der gerade betrachteten Kante von u nach v entsteht ein gerichteter Zyklus. In einem DAG ist dieser Fall ausgeschlossen; auch eine Schleife würde sofort auf einen grauen Knoten zeigen.
Damit gilt in jedem zulässigen Fall: v wird vor u abgeschlossen. Nach Umkehrung der Abschlussliste steht u vor v. Die vollständige Suche erfasst zudem jeden Knoten genau einmal. Beides zusammen ergibt eine topologische Ordnung.
Warum die Besuchsreihenfolge nicht genügt
Warum die Besuchsreihenfolge nicht genügt
Ein kleiner DAG hat nur die beiden Kanten A nach C und B nach C. Beginnt die DFS bei A, besucht sie A und danach C. C wird abgeschlossen, dann A. Anschließend muss die vollständige Suche noch beim weißen Knoten B beginnen; C ist dort schon schwarz.
Die Besuchsfolge A, C, B ist ungültig, weil B vor C stehen müsste. Die Abschlussfolge ist C, A, B. Ihre Umkehrung B, A, C ist dagegen gültig.
Der Unterschied ist kein Detail: „Zum ersten Mal gesehen“ bedeutet nicht „alle von hier erreichbaren Nachfolger bearbeitet“. Erst der Abschluss liefert die für diese Methode nötige Information.
DFS kann eine topologische Ordnung liefern, aber nicht durch bloßes Aufschreiben der ersten Besuche.
Laufzeit und benötigter Speicher
Schreibe für die Knotenzahl und für die Kantenzahl. Bei Adjazenzlisten hat jeder Knoten eine Liste seiner ausgehenden Nachbarn. Das Initialisieren der Zähler kostet , das Zählen aller eingehenden Kanten . Jeder Knoten wird höchstens einmal eingereiht und entnommen; jede Kante wird beim Verarbeiten ihres Anfangsknotens einmal betrachtet. Bei Warteschlangenoperationen in konstanter Zeit ergibt sich insgesamt .
Die Eingangsgrade, Warteschlange und Ausgabe brauchen zusätzlich Speicher. Der bereits gespeicherte Graph selbst benötigt mit Adjazenzlisten Speicher. Auch die vollständige DFS läuft in Zeit und benötigt bis zu zusätzlichen Speicher für Zustände, Abschlussliste und aktive Aufrufe.
Die Datenstruktur gehört zur Laufzeitaussage. Bei einer Adjazenzmatrix muss man für jeden Knoten eine ganze Zeile nach Nachbarn absuchen; so kann der Aufwand betragen. Wenn du aus einem gewöhnlichen Array vorne löschst und jedes Mal alle übrigen Einträge verschiebst, ist auch die Warteschlange nicht automatisch konstant schnell. Ein vorwärts laufender Leseindex oder eine passende Queue vermeidet dieses Verschieben.
Reihenfolge, Parallelität und Zeitplan verwechseln
Reihenfolge, Parallelität und Zeitplan verwechseln
„Kahn verwendet eine Warteschlange, also ist das einfach eine Breitensuche. Seine Ausgabe nennt automatisch die schnellste Bearbeitung und genau die Aufgaben, die parallel laufen.“
Eine Breitensuche erreicht einen Knoten bereits über einen passenden Suchweg; Kahn gibt ihn erst frei, wenn alle eingehenden Voraussetzungen erledigt sind. Eine topologische Ordnung ist zunächst eine zulässige lineare Reihenfolge. Sie kennt ohne weitere Angaben keine Bearbeitungsdauern, verfügbaren Personen oder Maschinen. Bereite Aufgaben können unter passenden Ressourcen parallel bearbeitet werden, aber die lineare Ausgabe allein ist noch kein optimaler Zeitplan.
Zusammenfassung
Eine topologische Ordnung enthält jeden Knoten genau einmal und richtet jede Kante von einer früheren zu einer späteren Position aus.
Ein endlicher gerichteter Graph besitzt genau dann eine solche Ordnung, wenn er azyklisch ist.
Kahn verwaltet die Eingangsgrade des Restgraphen und gibt nur Knoten ohne noch offene Voraussetzung aus.
Ein nichtleerer Rest bei leerer Queue beweist einen Zyklus; nicht jeder Restknoten muss selbst auf einem Zyklus liegen.
Die vollständige DFS liefert bei einem DAG durch Umkehrung der Abschlussreihenfolge eine topologische Ordnung.
Mit Adjazenzlisten und passenden Datenstrukturen laufen beide Verfahren in linearer Zeit bezüglich Knoten und Kanten.
Mehrere bereite Knoten erlauben verschiedene gültige Ordnungen; ein zulässiger Ablauf ist noch kein optimaler Zeitplan.
Übungen
Welche Knoten des Arbeitsplans mit A bis G haben anfangs Eingangsgrad 0?
A und B sind ausgegeben, C und D noch nicht. Welchen aktuellen Eingangsgrad hat E?
Führe Kahn am Arbeitsplan mit FIFO aus. Anfangs steht A vor B in der Queue; ausgehende Nachbarn werden alphabetisch betrachtet. Notiere die Ausgabe und erkläre, warum D vor C erscheint.
Ein Graph hat A nach B, B nach A und B nach C. Kahn kann keinen Knoten ausgeben. Welche Aussage ist richtig?
Jedes Arbeitspaket A bis G dauert genau eine Zeiteinheit. Es gibt beliebig viele Arbeitskräfte. Eine Aufgabe darf erst starten, wenn alle ihre Vorgänger fertig sind. Wie viele Zeiteinheiten braucht der Arbeitsplan mindestens?
Beweise für einen DAG: Seine topologische Ordnung ist genau dann eindeutig, wenn in jedem Schritt von Kahn nur ein Knoten bereit ist.
Ein DAG hat nur die Kanten A nach C und B nach C. Die vollständige DFS beginnt bei A und anschließend, falls nötig, bei B. Gib Besuchs- und Abschlussfolge an. Welche Folge musst du für eine topologische Ordnung umkehren?