I
n diesem Blog-Artikel stellen wir einen effizienten Graphen-Algorithmus vor, nämlich die Erzeugung einer topologischen Sortierung. Dies ist eine bestimmte Reihenfolge der Knoten eines zusammenhängenden, kreisfreien, gerichteten Graphen. Wir stellen zunächst das Problem vor, das wir sowohl aus der Ablaufplanung als auch aus der Software-Entwicklung motivieren. Danach skizzieren wir einen überraschend einfachen effizienten Algorithmus. Für diesen stellen wir dann eine elegante Implementierung in C#1 vor.
I. DEFINITION & MOTIVATION
Die Eingabe unseres Algorithmus besteht aus einem Graphen
2 mit
n Knoten. Die Kanten sind
gerichtet; dies bedeutet, dass eine Kante immer
von einem Knoten
u zu einem Knoten
v verläuft. Ist dies der Fall, wird
u als Vorgänger von
v und
v als Nachfolger von
u bezeichnet. Um die verschiedenen Rollen der beteiligten Knoten anzudeuten, werden in visuellen Darstellungen Pfeile verwendet. Fig. 1 zeigt ein Beispiel eines solchen Graphen.
Eine
topologische Sortierung ist eine Reihenfolge der Knoten, bei der für jeden Knoten
u alle seine Nachfolger
v später vorkommen als
u – wir möchten also die Knoten in eine Reihenfolge bringen, in der die Kanten immer nur „nach rechts“ zeigen. Fig. 3 zeigt eine solche Reihenfolge. Dabei fällt auf, dass eine topologische Sortierung in der Regel nicht eindeutig ist; beispielsweise können
L,
M und
K beliebig vertauscht werden.
Das Problem der Bestimmung einer topologischen Sortierung wollen wir zunächst aus der
Ablaufplanung motivieren. Wir stellen uns dazu vor, dass die Knoten des Graphen zu erledigende Aufgaben sind. Die Kanten stellen dabei Reihenfolgebedingungen dar. Verläuft eine Kante von
A nach
B, so muss
A vor
B erledigt werden – beispielsweise muss bei
A ein Werkzeug abgeholt werden, dass zur Durchführung von
B nötig ist.
Zur Motivation aus der
Software-Entwicklung stellen wir uns vor, dass programmatisch ein SQL-Statement erzeugt werden soll. Genauer sollen die Fremdschlüsselbeziehungen einer Menge von Datenbanktabellen in Join-Statements verwendet werden. Dazu ist es nötig, die Tabellen in eine Reihenfolge zu bringen, bei der in den Join-Bedingungen
weiter rechts im Statement stehender Join-Faktoren nur Tabellen vorkommen, die bereits
weiter links im Statement aufgetreten sind.
II. EIN ALGORITHMUS FÜR TOPOLOGISCHE SORTIERUNG
Der Begriff der topologischen Sortierung ist seit spätestens 1930
3 in der Fachliteratur nachweisbar und wird typischerweise in Algorithmik-Lehrbüchern
4 behandelt; die Erzeugung einer topologischen Sortierung war ferner Algorithmus der Woche
5 im Informatik-Jahr 2006.
Üblicherweise wird zum Erzeugen einer topologischen Sortierung ein Algorithmus vorgestellt, der auf iterativer Suche von Knoten mit Eingangsgrad 0 basiert, wobei der Eingangsgrad etwa in einem unterstützenden Array verwaltet wird. Ein Knoten ohne Vorgänger wird dann als nächster Kandidat in die topologische Sortierung übernommen und der Eingangsgrad aller seiner Nachfolger dekrementiert. Dieser Algorithmus kann stackfrei
6 implementiert werden, was ihn für den Einsatz in sehr eingeschränkten technischen Umgebungen attraktiv macht.
Interessanterweise kann aber eine topologische Sortierung auch durch modifizierte Tiefensuche
7 erzeugt werden. Fig. 2 zeigt einen DFS-Wald (mit etwas suggestivem Layout) für den Graphen
8 aus Fig. 1, wobei die Zahlen in den Knoten die Besuchsreihenfolge angeben. Bäume stellen wir so dar, dass die Wurzel oben ist – dies ist passend, denn „in der Informatik wachsen die Bäume nicht in den Himmel“
9. In Fig. 2 geben die Zahlen an den Knoten jeweils die Reihenfolge an, in der mit dem Besuch des Knotens begonnen wird. Die gezeigten Kanten sind Baumkanten, während Vorwärts-, Rückwärts- und Querkanten nicht gezeigt werden. Da der Graph aus Fig. 1 nicht stark zusammenhängend ist, muss die Tiefensuche insgesamt zweimal begonnen werden, in unserem Beispiel in
A und
J.