Robert Sedgewick: Algorithmen

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


32. Gerichtete Graphen



Transitive Hülle

In ungerichteten Graphen sind durch den einfachen Zusammenhang die Knoten gegeben, die von einem gegebenen Knoten aus erreicht werden können, indem Kanten des Graphen durchlaufen werden: Es sind alle Knoten, die der gleichen zusammenhängenden Komponente angehören. In ähnlicher Weise interessiert uns bei gerichteten Graphen oft die Menge der Knoten, die von einem gegebenen Knoten aus erreicht werden können, indem Kanten des Graphen in der angegebenen Richtung durchlaufen werden. Das Problem ist bei gerichteten Graphen wesentlich komplizierter als der einfache Zusammenhang.

Es läßt sich leicht beweisen, daß die rekursive Prozedur visit aus dem in Kapitel 29 angegebenen Tiefensuchverfahren alle Knoten besucht, die vom Anfangsknoten aus erreicht werden können. Wenn wir daher diese Prozedur so modifizieren, daß die Knoten ausgegeben werden, die von ihr besucht werden (etwa durch Einfügen von write(name(k)) unmittelbar am Anfang), so geben wir alle Knoten aus, die vom Anfangsknoten aus erreicht werden können. Es ist jedoch zu beachten, daß nicht notwendigerweise die Aussage gilt, daß jeder Baum im Tiefensuch-Wald alle Knoten enthält, die von der Wurzel dieses Baums aus erreicht werden können: In unserem Beispiel können von H aus alle Knoten im Graph erreicht werden, nicht nur I. Um für jeden Knoten alle Knoten zu erhalten, die von ihm aus besucht werden können, rufen wir einfach V mal visit auf, einmal für jeden Knoten:

    for k:=1 to V do
      begin
      id:=0;
      for j:=1 to V do val[j]:=0;
      visit(k);
      writeln
      end;

Dieses Programm erzeugt für den gerichteten Graph in Abbildung 32.1 die folgende Ausgabe. Wie zuvor hängt die Anordnung der Namen der Knoten in jeder Zeile von der verwendeten speziellen Darstellung des Graphen und der benutzten Suchprozedur ab. Die Menge der Knoten in jeder Zeile ist eine Struktureigenschaft des Graphen selbst: Jede Zeile enthält diejenigen Knoten, die vom ersten Knoten in der Zeile über einen gerichteten Pfad erreichbar sind.

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

Für ungerichtete Graphen würde diese Berechnung eine Tabelle mit der Eigenschaft erzeugen, daß jedem Knoten in einer zusammenhängenden Komponente eine Zeile entspricht, in der alle in dieser Komponente enthaltenen Knoten aufgezählt sind. Die obige Tabelle besitzt eine ähnliche Eigenschaft: In einigen der Zeilen sind identische Mengen von Knoten aufgeführt. Weiter unten betrachten wir die Verallgemeinerung des Zusammenhangbegriffs, die diese Eigenschaft erklärt.

Wie gewöhnlich könnten wir Programmabschnitte hinzufügen, um eine zusätzliche Verarbeitung vorzunehmen, anstatt nur die Tabelle auszugeben. Eine Operation, die wir vielleicht ausführen möchten, ist das Hinzufügen einer Kante direkt von x nach y, wenn ein Weg existiert, um von x nach y zu gelangen. Der Graph, der durch das Hinzufügen aller Kanten dieser Art zu einem gerichteten Graph entsteht, wird die transitive Hülle des Graphen genannt. Im Normalfall wird dabei eine große Anzahl von Kanten hinzugefügt, und die transitive Hülle ist meist dicht, so daß eine Darstellung mittels Adjazenzmatrix benutzt wird. Hierbei existiert eine Analogie zu zusammenhängenden Komponenten in einem ungerichteten Graph: Wenn wir diese Berechnung erst einmal ausgeführt haben, können wir schnell Fragen beantworten wie: »Existiert ein Weg, um von x nach y zu gelangen?«

Eigenschaft 32.1 Mittels Tiefensuche läßt sich die transitive Hülle eines gerichteten Graphen in O(V(E + V)) Schritten für einen lichten Graph und in O(V3) Schritten für einen dichten Graph zu berechnen.

Dies folgt unmittelbar aus den grundlegenden Eigenschaften in Kapitel 29: Wir führen die dort angegebene Tiefensuchprozedur für jeden der V Knoten im Graph aus. Das gleiche Ergebnis gilt für Breitensuche; wie oben erwähnt, ist die Reihenfolge, in der wir die Knoten besuchen, für dieses Problem nicht weiter wesentlich. w.z.b.w.

Es existiert ein bemerkenswert einfaches nichtrekursives Programm zur Berechnung der transitiven Hülle eines Graphen, der mittels einer Adjazenzmatrix dargestellt ist:

    for y:=1 to V do
      for x:=1 to V do
        if a[x,y] then
          for j:=1 to V do
            if a[y,j] then a[x,j]:=true;

S. Warshall entwickelte dieses Verfahren 1962, unter Benutzung der einfachen Bemerkung, daß, »falls ein Weg existiert, um von Knoten x nach Knoten y zu gelangen, und ein Weg, um von Knoten y nach Knoten j zu gelangen, auch ein Weg existiert, um von Knoten x nach Knoten j zu gelangen.« Der Trick besteht darin, diese Aussage etwas zu verstärken, so daß die Berechnung in nur einem Durchlauf durch die Matrix ausgeführt werden kann, nämlich: »Falls ein Weg existiert, um von Knoten x nach Knoten y zu gelangen, unter ausschließlicher Verwendung von Knoten mit Indizes, die kleiner als y sind, und ein Weg, um von Knoten y nach Knoten j zu gelangen, so existiert auch ein Weg, um von Knoten x nach Knoten j zu gelangen, unter ausschließlicher Verwendung von Knoten mit Indizes, die kleiner als y + 1 sind.« Das obige Programm ist eine direkte Implementation dieser Aussage.

Abbildung 32.3
Abbildung 32.3 Anfangsetappen des Algorithmus von Warshall.

Mit dem Verfahren von Warshall wird die Adjazenzmatrix eines Graphen in die Adjazenzmatrix seiner transitiven Hülle umgewandelt. Eine Möglichkeit, dem Algorithmus zu folgen, besteht darin, sich ihn in der Weise vorzustellen, daß jedesmal in einer ganzen Zeile der Matrix auf einmal Werte gesetzt werden. Die Operation für Spalte y besteht darin, jede Zeile mit einer Eins in Spalte y durch das Ergebnis der OR-Verknüpfung dieser Zeile und Zeile y zu ersetzen. Abbildung 32.3 zeigt die ursprüngliche Matrix für unseren Beispiel-Graphen und den Zustand der Matrix nach der Verarbeitung der ersten zwei und der Hälfte der dritten Spalte; bis zu diesem Moment wurde nur Zeile C verändert. Abbildung 32.4 zeigt die Matrix vor der Verarbeitung der letzten Spalten sowie das Endergebnis (die transitive Hülle).

Abbildung 32.4
Abbildung 32.4 Letzte Etappen des Algorithmus von Warshall.

Eigenschaft 32.2 Der Algorithmus von Warshall ermöglicht die Berechnung der transitiven Hülle in O(V3) Schritten.

Falls die Matrix ursprünglich mit Einsen gefüllt ist, ist dies aufgrund der dreifach verschachtelten Schleifen offensichtlich. Doch selbst bei einem lichten Graph kann leicht dieser Fall eintreten; wenn zum Beispiel der erste Knoten mit jedem anderen Knoten verbunden ist, wird die Matrix mit Einsen gefüllt, bevor y auf 2 gesetzt wird. w.z.b.w.

Bei sehr großen Graphen kann diese Berechnung so organisiert werden, daß die Bit-Operationen jedesmal für ein Computerwort ausgeführt werden, was in vielen Umgebungen zu erheblichen Einsparungen führt.


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