Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


32. Gerichtete Graphen



Topologisches Sortieren

Zyklische Graphen treten in vielen Anwendungen auf, in denen gerichtete Graphen eine Rolle spielen. Wenn der Graph in Abbildung 32.1 zur Modellierung einer Fertigungsstraße dienen würde, so würde daraus beispielsweise folgen, daß Arbeitsgang A vor Arbeitsgang G ausgeführt werden muß, welcher vor Arbeitsgang C ausgeführt werden muß, welcher vor Arbeitsgang A ausgeführt werden muß. Doch eine solche Situation ist in sich widersprüchlich; für diese und viele andere Anwendungen werden gerichtete Graphen ohne gerichtete Zyklen (Zyklen, bei denen alle Kanten in der gleichen Richtung zeigen) benötigt. Derartige Graphen werden gerichtete azyklische Graphen (directed acyclic graphs, abgekürzt dags) genannt. Dags können viele Zyklen aufweisen, wenn die Richtungen der Kanten nicht berücksichtigt werden; ihre definierende Eigenschaft besagt einfach, daß man niemals einen Zyklus durchlaufen kann, wenn man den Kanten in der angegebenen Richtung folgt. Abbildung 32.8 zeigt einen dag, der dem gerichteten Graph in Abbildung 32.1 ähnlich ist, wobei ein paar Kanten entfernt oder in der Richtung geändert wurden, um Zyklen zu beseitigen. Die Liste der Kanten für diesen Graph ist die gleiche wie für den zusammenhängenden Graph aus Kapitel 30, doch auch hier bewirkt die Reihenfolge der Knoten bei der Angabe der Kante einen Unterschied.

Abbildung 32.8
Abbildung 32.8 Ein gerichteter azyklischer Graph.

Dags unterscheiden sich tatsächlich sehr stark von allgemeinen gerichteten Graphen; in gewissem Sinne sind sie teils Baum, teils Graph. Bei ihrer Verarbeitung läßt sich sicher ihre spezielle Struktur ausnutzen. Von einem beliebigen Knoten aus betrachtet sieht ein dag wie ein Baum aus; anders gesagt, der Tiefensuch-Wald für einen dag hat keine nach oben führenden Kanten. Abbildung 32.9 zeigt den Tiefensuch-Wald, der die Arbeitsweise von dfs bei Anwendung auf den dag in Abbildung 32.8 beschreibt.

Abbildung 32.9
Abbildung 32.9 Tiefensuche in einem dag.

Eine grundlegende Operation mit dags ist die Verarbeitung der Knoten des Graphen in einer solchen Reihenfolge, daß kein Knoten vor einem auf ihn zeigenden Knoten verarbeitet wird. Die Knoten im obigen Graph könnten zum Beispiel in der folgenden Reihenfolge verarbeitet werden:

J K L M A G H I F E D B C

Zeichnet man zu den in diesen Positionen angeordneten Knoten die Kanten, so verlaufen sie alle von links nach rechts. Wie bereits erwähnt, gibt es hierfür offensichtliche Anwendungen, zum Beispiel bei Graphen, die Fertigungsprozesse darstellen, denn es wird eine spezielle Vorgehensweise im Rahmen der durch den Graph vorgegebenen Einschränkungen angegeben. Diese Operation wird topologisches Sortieren genannt, da sie das Ordnen der Knoten des Graphen erfordert.

Im allgemeinen ist die Reihenfolge der Knoten, die durch ein topologisches Sortieren erzeugt wird, nicht eindeutig. Zum Beispiel ist die Reihenfolge

A J G F K L E M B H C I D

eine zulässige topologische Ordnung für unser Beispiel (und es gibt viele andere). Bei der erwähnten Anwendung bei der Fertigung tritt diese Situation auf, wenn ein Arbeitsgang nicht direkt oder indirekt von einem anderen abhängt und daher in dieser oder jener Reihenfolge ausgeführt werden kann.

Gelegentlich ist es nützlich, die Kanten in einem Graph auf umgekehrte Weise zu definieren, indem man sagt, daß eine von x nach y gerichtete Kante bedeutet, daß Knoten x von Knoten y »abhängt«. Die Knoten könnten zum Beispiel Begriffe darstellen, die in einem Handbuch einer Programmiersprache (oder einem Buch über Algorithmen!) definiert werden sollen, wobei eine Kante von x nach y führt, falls y in der Definition von x benutzt wird. In diesem Falle wäre es von Nutzen, eine Reihenfolge mit der Eigenschaft zu finden, daß jeder Begriff definiert wird, bevor er in einer anderen Definition verwendet wird. Dies entspricht der Anordnung der Knoten in einer Zeile in der Weise, daß alle Kanten von rechts nach links verlaufen. Eine umgekehrte topologische Reihenfolge für den Graph aus unserem Beispiel ist:

D E F C B I H G A K M L J

Der Unterschied ist hierbei nicht von größerer Bedeutung: Die Ausführung eines umgekehrten topologischen Sortierens für einen Graph ist äquivalent zur Ausführung eines topologischen Sortierens für den Graph, den man durch Umkehrung der Richtung aller Kanten erhält.

Wir haben jedoch schon einen Algorithmus für das umgekehrte topologische Sortieren kennengelernt: Die standardmäßige rekursive Tiefensuchprozedur aus Kapitel 29! Wenn der eingegebene Graph ein dag ist, bewirkt eine einfache Änderung von visit in der Weise, daß vor dem Verlassen der Prozedur der gerade besuchte Knoten ausgegeben wird (zum Beispiel durch Einfügen von write(name[k]) unmittelbar am Ende), daß dfs die Knoten in der umgekehrten topologischen Reihenfolge ausgibt. Daß dies zum Ziel führt, läßt sich leicht mittels Induktion beweisen: Wir geben den Namen jedes Knotens aus, nachdem wir die Namen aller der Knoten ausgegeben haben, auf die er zeigt. Wenn visit in dieser Weise geändert und auf unser Beispiel angewandt wird, werden die Knoten in der oben angegebenen umgekehrten topologischen Reihenfolge ausgegeben. Die Ausgabe des Knotennamens beim Verlassen dieser rekursiven Prozedur entspricht genau dem Ablegen des Knotennamens in einem Stapel beim Eintreten und dem Entnehmen und Ausgeben dieses Namens beim Verlassen. In diesem Falle gibt es keinen Grund, einen expliziten Stapel zu verwenden, da ihn die Rekursion automatisch bereitstellt; für das nachfolgend betrachtete kompliziertere Problem werden wir jedoch einen Stapel benötigen.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]