Robert Sedgewick: Algorithmen

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


32. Gerichtete Graphen



Tiefensuche

Der Tiefensuch-Algorithmus aus Kapitel 29 ist für gerichtete Graphen genau in der angegebenen Form anwendbar. In Wirklichkeit ist seine Arbeitsweise sogar noch etwas einfacher als bei ungerichteten Graphen, da keine doppelten Kanten zwischen Knoten beachtet werden müssen, außer wenn sie explizit in den Graph aufgenommen werden. Die Suchbäume haben jedoch eine etwas kompliziertere Struktur. Zum Beispiel zeigt Abbildung 32.2 die Tiefensuch-Struktur, die die Arbeitsweise des rekursiven Algorithmus aus Kapitel 29 bei Anwendung auf unseren Beispiel-Graphen beschreibt. Wie zuvor ist dies eine in anderer Form gezeichnete Variante des Graphen: Als durchgehende Linien dargestellte Kanten entsprechen denjenigen Kanten, die tatsächlich benutzt wurden, um über rekursive Aufrufe Knoten zu besuchen, und gestrichelt gezeichnete Kanten entsprechen denjenigen Kanten, die auf Knoten zeigen, die zu dem Zeitpunkt, als die Kante betrachtet wurde, schon besucht worden waren. Die Knoten werden in der Reihenfolge A F E D B G J K L M C H I besucht.

Abbildung 32.2
Abbildung 32.2 Tiefensuch-Wald für einen gerichteten Graph.

Beachten Sie, daß die Richtungen der Kanten bewirken, daß sich dieser Tiefensuch-Wald von den Tiefensuch-Wäldern für ungerichtete Graphen stark unterscheidet. Zum Beispiel ist, obwohl der ursprüngliche Graph zusammenhängend war, die durch die durchgehenden Kanten definierte Struktur der Tiefensuche nicht zusammenhängend; es ist ein Wald, kein Baum.

Bei ungerichteten Graphen trat nur eine Art von gestrichelten Kanten auf, nämlich Kanten, die einen Knoten mit einem bestimmten Vorgänger im Baum verbinden. Bei gerichteten Graphen gibt es drei Arten von gestrichelten Kanten: nach oben verlaufende Kanten, die von einem Knoten zu einem bestimmten Vorgänger im Baum zeigen, nach unten verlaufende Kanten, die von einem Knoten zu einem bestimmten Nachfolger im Baum zeigen, und quer verlaufende Kanten, die von einem Knoten zu einem anderen Knoten führen, der weder ein Nachfolger noch ein Vorgänger im Baum ist.

Wie im Falle ungerichteter Graphen interessieren uns auch bei gerichteten Graphen Zusammenhangseigenschaften. Wir möchten in der Lage sein, Fragen der Art »Existiert ein gerichteter Pfad von Knoten x nach Knoten y (ein Pfad, der Kanten nur längs der angegebenen Richtung folgt)?«, »Welche Knoten können wir von x aus über einen gerichteten Pfad erreichen?« und »Existiert ein gerichteter Pfad von Knoten x nach Knoten y und ein gerichteter Pfad von y nach x?« zu beantworten. Genau wie bei ungerichteten Graphen wird es uns möglich sein, solche Fragen zu beantworten, indem wir den grundlegenden Algorithmus der Tiefensuche in geeigneter Weise modifizieren, obwohl die Existenz mehrerer unterschiedlicher Typen von gestrichelten Kanten bewirkt, daß die Modifikationen etwas komplizierter sind.


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