Robert Sedgewick: Algorithmen

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


32. Gerichtete Graphen



Gerichtete Graphen sind Graphen, in denen die die Knoten verbindenden Kanten eine Richtung haben; diese zusätzliche Struktur führt dazu, daß die Bestimmung verschiedener Eigenschaften schwieriger wird. Die Verarbeitung solcher Graphen ist mit dem Umherfahren in einer Stadt mit vielen Einbahnstraßen vergleichbar; in einer solchen Situation kann es wirklich eine komplizierte Aufgabe sein, von einem Ort zu einem anderen zu gelangen.

Oft spiegelt die Richtung der Kante eine Art Reihenfolgebeziehung bei der zu modellierenden Anwendung wider. Zum Beispiel könnte ein gerichteter Graph benutzt werden, um eine Fertigungsstraße zu modellieren; Knoten entsprechen auszuführenden Arbeitsgängen, und von Knoten x nach Knoten y existiert eine Kante, wenn der dem Knoten x entsprechende Arbeitsgang vor dem dem Knoten y entsprechenden Arbeitsgang ausgeführt werden muß. Wie legen wir fest, wann die einzelnen Arbeitsgänge auszuführen sind, so daß keine der Vorrangbedingungen verletzt wird?

Im vorliegenden Kapitel betrachten wir die Tiefensuche für gerichtete Graphen sowie Algorithmen für die Berechnung der transitiven Hülle (die Informationen über den Zusammenhang zusammenfaßt), für topologisches Sortieren und für die Berechnung von streng zusammenhängenden Komponenten (die etwas mit Vorrangbeziehungen zu tun haben).

Wie in Kapitel 29 erwähnt, sind Darstellungen für gerichtete Graphen einfache Erweiterungen (eigentlich Einschränkungen) von Darstellungen für ungerichtete Graphen. Bei der Darstellung mittels Adjazenzliste erscheint jede Kante nur einmal: Die Kante, die von x nach y führt, ist als ein y enthaltender Listenknoten in der x entsprechenden verketteten Liste dargestellt. Bei der Darstellung mittels Adjazenzmatrix müssen wir eine vollständige VxV-Matrix beibehalten, mit einer Eins in Zeile x und Spalte y (doch nicht notwendigerweise in Zeile y und Spalte x), wenn eine von x nach y führende Kante existiert.

Ein gerichteter Graph, der dem von uns betrachteten ungerichteten Graph ähnlich ist, ist in Abbildung 32.1 dargestellt. Dieser Graph besteht aus den Kanten AG AB CA LM JM JL JK ED DF HI FE AF GE GC HG GJ LG IH ML. Die Reihenfolge, in der die Knoten bei der Angabe der Kanten erscheinen, ist nunmehr wesentlich: Die Schreibweise AG bezeichnet eine Kante, die von A nach G führt, jedoch nicht von G nach A. Es ist aber möglich, daß zwischen zwei Knoten zwei Kanten vorhanden sind, eine in jeder Richtung (Abbildung 32.1 enthält sowohl HI als auch IH und sowohl LM als auch ML).

Abbildung 32.1
Abbildung 32.1 Ein gerichteter Graph.

Wir bemerken, daß bei diesen Darstellungen zwischen einem ungerichteten Graph und einem gerichteten Graph, der anstelle jeder Kante im ungerichteten Graph zwei in entgegengesetzter Richtung verlaufende Kanten besitzt, kein Unterschied feststellbar wäre. Daher können einige der Algorithmen im vorliegenden Kapitel als Verallgemeinerungen von Algorithmen aus vorangegangenen Kapiteln betrachtet werden.


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