Lektion 4.5

Topologisches Sortieren

50 min Lesezeit
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.

Vermute zuerst

Zwei Aufgaben A und B haben keine unerledigten Voraussetzungen. Muss ein korrekter Plan mit A beginnen?

Beispiel

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.

KnotenArbeitspaketUnmittelbare Voraussetzungen
AQuellen sammelnkeine
BFormat festlegenkeine
CInhalte gliedernA und B
DBilder prüfenA
ESeiten setzenC und D
FAufgaben prüfenB und C
GMaterial veröffentlichenE 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.

Definition

Topologische Ordnung und DAG

Sei G=(V,E)G=(V,E) ein endlicher gerichteter Graph. VV ist seine Knotenmenge, EE seine Kantenmenge. Eine topologische Ordnung ist eine Liste aller Knoten, in der jeder Knoten genau einmal vorkommt und bei jeder Kante (u,v)(u,v) der Knoten uu vor vv steht. Bezeichnet p(v)p(v) die Position von vv in der Liste, lautet die Bedingung p(u)<p(v)p(u)<p(v) für alle Kanten (u,v)(u,v).

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.

Beispiel

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.

Kurz geprüft

Welche Folge erfüllt alle Abhängigkeiten des Arbeitsplans?

Satz

Eine Ordnung existiert genau für DAGs

Ein endlicher gerichteter Graph besitzt genau dann eine topologische Ordnung, wenn er keinen gerichteten Zyklus enthält.

Definition

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.

Schritt für Schritt

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.

  1. Zähle zunächst für jeden Knoten alle eingehenden Kanten. Trage jeden Knoten mit Eingangsgrad 0 genau einmal in die Warteschlange ein.

Schritt 1 von 4
Beispiel

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 EingangsgradeWarteschlange danach
noch keinerA: 0, B: 0, C: 2, D: 1, E: 2, F: 2, G: 2A, B
AC: 2 auf 1; D: 1 auf 0B, D
BC: 1 auf 0; F: 2 auf 1D, C
DE: 2 auf 1C
CE: 1 auf 0; F: 1 auf 0E, F
EG: 2 auf 1F
FG: 1 auf 0G
Gkeine ausgehende Kanteleer

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.

Abhängigkeiten Schritt für Schritt freigeben

Topologische Sortierung · Abhängigkeiten

Jede Kante heißt „erst das eine, dann das andere“, wie Module in einem Studienplan. Gesucht ist eine Reihenfolge, die alle Voraussetzungen einhält.

Gerichteter Graph · 7 Knoten · 9 Kanten

Aein = 0Bein = 0Cein = 2Dein = 1Eein = 2Fein = 2Gein = 2
Einsortiert
0
Kanten gestrichen
0
  • bereit
  • in Arbeit
  • einsortiert
  • auf einem Kreis
  • wartet hinter einem Kreis
  • gestrichen
  • Kreis
Schritt 1 von 18
Tempo
← → Schritt, Leertaste Abspielen
Start

Eingangsgrade zählen

Eine topologische Sortierung ordnet die Knoten so, dass jede Kante von vorn nach hinten zeigt, wie ein Zeitplan, in dem nichts vor seinen Voraussetzungen kommt. Der Eingangsgrad ein[v] zählt, wie viele Kanten in v hineinführen, also wie viele Voraussetzungen v noch hat. Ohne Voraussetzung sind: A, B. Sie dürfen sofort an die Reihe, in alphabetischer Reihenfolge.

Bereit (Eingangsgrad 0)

Vorne wird entnommen, hinten angefügt.

  1. B

Werte der Knoten

KnotenZustandeinPlatz
Awartet0–
Bwartet0–
Cunbekannt2–
Dunbekannt1–
Eunbekannt2–
Funbekannt2–
Gunbekannt2–

ein: Offene Voraussetzungen (Eingangsgrad) · Platz: Platz in der Reihenfolge

Pseudocoden = 7, m = 9
  1. ein[v] ← Anzahl der Kanten, die in v enden; Q ← alle v mit ein[v] = 0
  2. solange Q nicht leer ist:
  3. u ← vorderster Knoten aus Q; u an die Reihenfolge anhängen
  4. für jede Kante u → v: Kante streichen
  5. ein[v] ← ein[v] − 1; wenn ein[v] = 0: v hinten an Q
  6. sind Knoten übrig: der Graph hat einen Kreis

Der Graph enthält dieselben sieben Knoten und neun Abhängigkeiten wie unser Arbeitsplan. Gehe schrittweise weiter und vergleiche Eingangsgrade, bereite Knoten und Ausgabe. Die Auswahlregel des Werkzeugs darf eine andere gültige Ordnung liefern als unser FIFO-Lauf.

Probier es aus

Satz

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.

Beispiel

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.

Kurz geprüft

Im gerade beschriebenen Restgraphen bleibt D übrig. Was folgt daraus?

Definition

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.

Satz

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.

Beispiel

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.

Definition

Laufzeit und benötigter Speicher

Schreibe n=∣V∣n=|V| für die Knotenzahl und m=∣E∣m=|E| für die Kantenzahl. Bei Adjazenzlisten hat jeder Knoten eine Liste seiner ausgehenden Nachbarn. Das Initialisieren der Zähler kostet O(n)O(n), das Zählen aller eingehenden Kanten O(m)O(m). 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 O(n+m)O(n+m).

Die Eingangsgrade, Warteschlange und Ausgabe brauchen zusätzlich O(n)O(n) Speicher. Der bereits gespeicherte Graph selbst benötigt mit Adjazenzlisten O(n+m)O(n+m) Speicher. Auch die vollständige DFS läuft in O(n+m)O(n+m) Zeit und benötigt bis zu O(n)O(n) 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 O(n2)O(n^2) 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.

Häufige Fehler

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.“

Richtig ist

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

Aufgabe 1Multiple Choice

Welche Knoten des Arbeitsplans mit A bis G haben anfangs Eingangsgrad 0?

Aufgabe 2Numerisch

A und B sind ausgegeben, C und D noch nicht. Welchen aktuellen Eingangsgrad hat E?

Aufgabe 3Freitext

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.

Aufgabe 4Multiple Choice

Ein Graph hat A nach B, B nach A und B nach C. Kahn kann keinen Knoten ausgeben. Welche Aussage ist richtig?

Aufgabe 5Numerisch

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?

Aufgabe 6Freitext

Beweise für einen DAG: Seine topologische Ordnung ist genau dann eindeutig, wenn in jedem Schritt von Kahn nur ein Knoten bereit ist.

Aufgabe 7Freitext

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?