Die zu sortierende Menge

Die zu sortierenden Objekte müssen bezüglich der Beziehung teilweise angeordnet werden können, damit sie topologisch sortierbar sind. Mathematisch bilden die Objekte die Elemente einer Menge ${\displaystyle M}$, die bezüglich einer Relation (Beziehung) ${\displaystyle R}$ die folgenden Eigenschaften hat:

Für jeweils beliebige Elemente ${\displaystyle a,b,c}$ der Menge ${\displaystyle M}$ und der Relation ${\displaystyle R}$ gilt:

1. Irreflexivität: ${\displaystyle \neg (a\,R\,a)}$ (${\displaystyle a}$ steht nicht mit ${\displaystyle a}$ in Relation)
2. Transitivität: Wenn ${\displaystyle a\,R\,b}$ und ${\displaystyle b\,R\,c}$, dann gilt ${\displaystyle a\,R\,c}$.

Übersetzt heißt dies:

1. Ich kann die Hose nicht vor der Hose anziehen.
2. Wenn ich das Unterhemd vor dem Pullover anziehen muss und den Pullover vor dem Mantel, so folgt daraus, dass ich das Unterhemd vor dem Mantel anziehen muss.

Die Menge ${\displaystyle M}$ bildet dann bezüglich der Relation ${\displaystyle R}$ eine strenge Halbordnung. Oft schreibt man statt ${\displaystyle R}$ auch einfach ${\displaystyle <}$, weil die Relation ähnliche Eigenschaften hat wie die Kleiner-Relation für Zahlen. (Allerdings hat die Kleiner-Relation noch einige weitere Eigenschaften, die man hier nicht unbedingt hat. So kann man bei der Kleiner-Relation von zwei verschiedenen Zahlen immer entscheiden, welche der beiden kleiner ist. Hier ist dies nicht verlangt. Im Beispiel wäre dies der Vergleich von Socken und Unterhemd: Man kann nicht sagen, dass eines davon zuerst angezogen werden muss.)

Üblicherweise wird jedoch nicht die ganze Relation ${\displaystyle R}$ angegeben, sondern nur eine ausreichende Teilmenge von direkten Vorgänger-Nachfolger-Paaren. Die Relation ${\displaystyle R}$ ist dann über den transitiven Abschluss der durch die übergebenen Paare definierten Relation gegeben. Beispielsweise besagt die komplette Relation ${\displaystyle R}$ für das Beispielproblem auch, dass das Unterhemd vor dem Mantel angezogen werden muss (wegen „Unterhemd vor Pullover“ und „Pullover vor Mantel“ folgt aus der Transitivität auch „Unterhemd vor Mantel“). Der transitive Abschluss besteht nun darin, diese Paare der Relation ${\displaystyle R}$ hinzuzufügen. Bei der Implementierung eines entsprechenden Sortieralgorithmus wird allerdings die vollständige Relation nicht explizit generiert.

Die topologisch sortierte Menge

Eine bestimmte Reihenfolge hingegen wird mathematisch durch eine strenge Totalordnung definiert: Für je zwei verschiedene Elemente ${\displaystyle a,b}$ aus ${\displaystyle M}$ ist festgelegt, ob ${\displaystyle a}$ vor ${\displaystyle b}$ oder ${\displaystyle b}$ vor ${\displaystyle a}$ kommt (Es steht z. B. fest, ob ich heute Morgen zuerst die Unterhose oder zuerst das Unterhemd angezogen habe). Die strenge Totalordnung ist also mathematisch definiert durch das zusätzliche Axiom der

• Trichotomie: Für beliebige Elemente ${\displaystyle a,b}$ aus ${\displaystyle M}$ gilt entweder ${\displaystyle a\,R\,b}$ oder ${\displaystyle a=b}$ oder ${\displaystyle b\,R\,a}$.

Die Aufgabe des topologischen Sortierens ist nun, zu einer gegebenen strengen Halbordnung ${\displaystyle R}$ eine Totalordnung ${\displaystyle {\tilde {R}}}$ zu finden, so dass für alle ${\displaystyle a,b}$ mit ${\displaystyle a\,R\,b}$ auch gilt ${\displaystyle a\,{\tilde {R}}\,b}$.

Definition der topologischen Sortierung

Motiviert durch die Untersuchungen der beiden vorhergehenden Abschnitte kann man nun den mathematischen Begriff einer topologischen Sortierung einführen:

Sei ${\displaystyle M}$ eine Menge und ${\displaystyle R\subseteq M\times M}$. Eine Menge ${\displaystyle T\subseteq M\times M}$ heißt genau dann eine topologische Sortierung von ${\displaystyle M}$ für ${\displaystyle R}$, wenn ${\displaystyle T}$ eine strenge Totalordnung auf ${\displaystyle M}$ ist und ${\displaystyle R\subseteq T}$ gilt.

Diese Definition beschränkt den Begriff einer topologischen Sortierung ausdrücklich nicht auf endliche Mengen, obwohl im Zusammenhang mit einer algorithmischen Untersuchung eine solche Beschränkung sinnvoll ist.

Azyklische Graphen und topologische Sortierungen

Den bereits erwähnten Zusammenhang von topologischen Sortierungen und azyklischen Graphen kann man in folgendem Satz zusammenfassen:

Sei ${\displaystyle M}$ eine Menge und ${\displaystyle R\subseteq M\times M}$. Dann sind äquivalent:

• Es gibt eine topologische Sortierung ${\displaystyle T}$ von ${\displaystyle M}$ für ${\displaystyle R}$
• ${\displaystyle (M,R)}$ ist ein azyklischer Digraph

Sortierbare Graphen

Graph 1 ist topologisch sortierbar. Es existieren mehrere Lösungen (zum Beispiel A B C G D E F). Dabei spielt es keine Rolle, dass mehrere Elemente ohne Vorgänger existieren (A und G), dass manche Elemente mehrere Nachfolger haben (B hat zum Beispiel drei Nachfolger) und manche mehrere Vorgänger (D und E).

Graph 2 ist ebenfalls topologisch sortierbar (zum Beispiel A C B D E), obwohl er nicht zusammenhängend ist.

Alle gerichteten Graphen, die keine Zyklen enthalten, sind topologisch sortierbar.

Nicht sortierbare Graphen

• Graph 3
• Graph 4
• Graph 5

Graph 3 ist nicht topologisch sortierbar, da er einen Zyklus, also eine gegenseitige Abhängigkeit enthält (Elemente B, C, E und D).

Auch wenn wie in Graph 4 nur zwei Elemente gegenseitig voneinander abhängen, ist eine topologische Sortierung unmöglich. Allgemein sind genau alle Graphen, die einen Kreis enthalten, nicht topologisch sortierbar. Topologische Sortierbarkeit ist logisch gleichwertig zur Azyklizität.

Graph 5 hat auch keine topologische Sortierung, nicht aber weil er einen „Kreis“ enthält, sondern weil er gegen die geforderte Irreflexivität verstößt. Knoten A steht mit sich selbst in Relation. Graph 5 ist also ein minimaler nicht topologisch sortierbarer Graph.

Einfache Version mit Markierung von Elementen

Der Sortieralgorithmus benötigt die Information, wie viele Vorgänger ein Element enthält (Vorgängeranzahl). Bereits gefundene Elemente müssen aus der Liste entfernt oder markiert werden. Man kann Elemente dadurch markieren, indem man die Vorgängeranzahl auf −1 setzt.

1. Berechne die Vorgängeranzahl:

• Setze die Vorgängeranzahl aller Elemente auf 0.
• Für alle Elemente durchlaufe die Nachfolgerliste und erhöhe die Vorgängeranzahl jedes dieser Elemente um 1.
  (Jetzt sind alle Vorgängerzahlen berechnet)

2. Solange (nicht markierte) Elemente in der Liste sind:

• Suche ein Element mit Vorgängeranzahl 0.
  Falls kein solches Element gefunden wird, ist eine topologische Sortierung nicht möglich, da gegenseitige Abhängigkeiten (Zyklen) bestehen. Der Algorithmus bricht mit einem Fehler ab.
• Gib das gefundene Element aus und entferne es aus der Liste oder markiere es (Setze zum Beispiel die Vorgängeranzahl gleich –1 als Markierung)
• Gehe die Liste der Nachfolger des gefundenen Elements durch und verringere die Vorgängeranzahl um 1. Das Element ist jetzt effektiv aus der Elementliste entfernt. Durch die Verringerung der Vorgängeranzahl können neue Elemente ohne Vorgänger entstehen.

Sind alle Elemente ausgegeben bzw. markiert, so war die topologische Sortierung erfolgreich.

Erweiterte Version mit einer zusätzlichen Hilfsliste

Um Elemente ohne Vorgänger schnell zu finden, kann eine zusätzliche Hilfsliste erzeugt werden. Diese wird nach der Berechnung der Vorgängerzahlen mit allen anfangs vorgängerlosen Elementen, also mit Vorgängerzahl gleich Null, gefüllt. In Phase 2 wird anstatt der Suche eines Elements mit Vorgängeranzahl Null einfach eines aus der Hilfsliste entnommen. Wird die Vorgängerzahl eines Elements während der Phase 2 bei der Verringerung um 1 gleich Null, so wird es in die Hilfsliste eingefügt. Der Algorithmus endet, wenn keine Elemente mehr in der Hilfsliste sind. Auf die Markierung kann dann ebenfalls verzichtet werden.

Average und Worst Case

Beim topologischen Sortieren mit n Elementen und m Beziehungen zwischen diesen gilt für „normale“ (Average Case) Probleme ${\displaystyle {\mathcal {O}}(m)={\mathcal {O}}(n)}$, da jedes Element im Schnitt nur eine konstante Zahl von Beziehungen hat. Im Extremfall (Worst Case) können in einem gerichteten azyklischen Graphen jedoch ${\displaystyle m=\sum _{i=1}^{n}(i-1)={\frac {n\cdot (n+1)}{2}}-n={\frac {n^{2}-n}{2}}={\mathcal {O}}(n^{2})}$ Beziehungen auftreten.

Erste Phase: Aufbau der Vorgängerzahlen

Die erste Phase setzt die Vorgängerzahlen auf 0 und benötigt n Schleifendurchläufe (${\displaystyle {\mathcal {O}}(n)}$). Für das Durchlaufen der m Nachfolger benötigt sie eine Zeit der Größenordnung ${\displaystyle {\mathcal {O}}(n)}$ (Average Case) oder ${\displaystyle {\mathcal {O}}(n^{2})}$ (Worst Case).

Hilfsliste für vorgängerlose Elemente

Vor der zweiten Phase wird eine Hilfsliste aufgebaut, die alle vorgängerlosen Elemente enthält (${\displaystyle {\mathcal {O}}(n)}$). Danach werden nur noch neue vorgängerlose in die Hilfsliste eingefügt (${\displaystyle {\mathcal {O}}(1)}$) und entnommen (${\displaystyle {\mathcal {O}}(1)}$). Die Suche nach vorgängerlosen Elementen beeinflusst das Zeitverhalten nicht. Gleiches kann man erreichen, indem man gefundene vorgängerlose Elemente „nach vorne“ verlagert (mit ${\displaystyle {\mathcal {O}}(1)}$ möglich).

Zweite Phase: Entnahme von vorgängerlosen Elementen

Die zweite Phase behandelt im Erfolgsfall alle n Elemente und verringert die Vorgängerzahl von im Schnitt ${\displaystyle {\frac {m}{n}}}$ Nachfolgern, das Zeitverhalten ist also ${\displaystyle {\mathcal {O}}(n)\cdot {\mathcal {O}}\left({\frac {m}{n}}\right)}$.

Gesamtverhalten

	Beziehungen m und Objekte n	Zeitverhalten (mit Hilfsliste)
Average-Case	${\displaystyle {\mathcal {O}}(m)={\mathcal {O}}(n)}$	${\displaystyle {\mathcal {O}}(n)}$
Worst-Case	${\displaystyle {\mathcal {O}}(m)={\mathcal {O}}(n^{2})}$	${\displaystyle {\mathcal {O}}(n^{2})}$

Ungünstiger Aufbau der Listen

Der Algorithmus in Niklaus Wirths Buch (siehe Literatur) enthält eine Einlesephase, in der er die Beziehungspaare in eine Liste einfügt, die wiederum Listen für die Nachfolger enthalten. Die jeweilige Nachfolgerliste ermittelt er durch eine lineare Suche (${\displaystyle {\mathcal {O}}(n)}$), die für jedes eingelesene Paar (${\displaystyle {\mathcal {O}}(m)}$) durchgeführt wird, insgesamt also ${\displaystyle {\mathcal {O}}(n)\cdot {\mathcal {O}}(m)}$ (quadratisch). Dies verschlechtert das gesamte Zeitverhalten. Der Aufbau der Listen könnte zum Beispiel über einen Bucketsort-Algorithmus aber auch in linearer Zeit ${\displaystyle {\mathcal {O}}(m)}$ bewerkstelligt werden.