Robert Sedgewick: Algorithmen

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


29. Elementare Algorithmen für Graphen



Tiefensuche

Zu Beginn dieses Kapitels sahen wir, daß bei der Verarbeitung eines Graphen sofort verschiedene Fragen auftreten. Ist der Graph zusammenhängend? Wenn nicht, welches sind seine zusammenhängenden Komponenten? Enthält der Graph einen Zyklus? Diese und viele andere Probleme können leicht mit einer Methode gelöst werden, die Tiefensuche genannt wird und einen natürlichen Weg darstellt, wie im Graph systematisch jeder Knoten »besucht« und jede Kante geprüft werden kann. In den folgenden Kapiteln werden wir sehen, daß einfache Variationen einer Verallgemeinerung dieses Verfahrens benutzt werden können, um eine Vielzahl von mit Graphen zusammenhängenden Problemen zu lösen.

Einstweilen konzentrieren wir uns auf die Methode, wie jedes Element des Graphen in einer systematischen Weise betrachtet werden kann. Wir beginnen mit einem Programm für Graphen, die mit Hilfe von Adjazenzlisten dargestellt sind:

    procedure listdfs;
      var id,k: integer;
          val: array[1..maxV] of integer;
      procedure visit(k: integer);
        var t: link;
        begin
        id:=id+1; val[k]:=id;
        t:=adj[k];
        while t<>z do
          begin
          if val[t^.v]=0 then visit(t^.v);
          t:=t^.next
          end
        end;
      begin
      id:=0;
      for k:=1 to V do val[k]:=0;
      for k:=1 to V do
        if val[k]=0 then visit(k)
      end;

Dieses Programm füllt, während es jeden Knoten eines Graphen besucht, ein Feld val[1..V]. Am Anfang werden alle Elemente des Felds auf null gesetzt, so daß val[k]=0 besagt, daß Knoten k noch nicht besucht worden ist. Das Ziel besteht darin, alle Knoten des Graphen systematisch zu besuchen und dabei für id = 1, 2, ...,V die Eintragung val für den id-ten besuchten Knoten auf id zu setzen. Das Programm verwendet eine rekursive Prozedur visit, die alle Knoten besucht, die sich in der gleichen zusammenhängenden Komponente befinden wie der als Argument gegebene Knoten. Um einen Knoten mittels visit zu durchlaufen, prüfen wir alle seine Kanten, um festzustellen, ob sie zu Knoten führen, die noch nicht besucht worden sind (was aus den Einträgen 0 in val hervorgeht); wenn das der Fall ist, besuchen wir sie mittels visit. Zunächst wird visit für den ersten Knoten aufgerufen, was zur Folge hat, daß für alle mit diesem Knoten verbundenen Knoten die entsprechenden Elemente von val auf von null verschiedene Werte gesetzt werden. Danach durchsucht listdfs das Feld val, um einen Null-Eintrag zu finden (der einem Knoten entspricht, der noch nicht betrachtet wurde), und ruft für diesen Knoten visit auf, wobei in dieser Weise so lange fortgefahren wird, bis alle Knoten besucht worden sind.

Abbildung 29.5 zeichnet die Vorgehensweise bei der Tiefensuche für die große Komponente des Graphen aus unserem Beispiel nach und zeigt, wie im Ergebnis des Aufrufs visit(1) jede Kante in dieser Komponente berührt wird (nachdem die in Abbildung 29.4 dargestellten Adjazenzlisten erzeugt worden sind). Tatsächlich wird jede Kante zweimal »berührt«, da jede Kante in beiden Adjazenzlisten der durch sie verbundenen Knoten dargestellt ist. Abbildung 29.5 enthält für jede durchlaufene Kante eine Skizze (jedesmal, wenn die Verbindung t gesetzt wird, so daß sie auf einen bestimmten Knoten in einer bestimmten Adjazenzliste zeigt). In jeder Skizze ist die »aktuelle« Kante schattiert, und der Knoten, dessen Adjazenzliste diese Kante enthält, ist mit einem Quadrat markiert. Zusätzlich ist jedesmal, wenn ein Knoten zum erstenmal besucht wird (was einem neuen Aufruf von visit entspricht), die Kante, die zu diesem Knoten führte, durch eine dicke Linie dargestellt. Knoten, die noch gar nicht berührt wurden, sind schattiert, doch nicht mit Buchstaben markiert, und Knoten, für die visit abgeschlossen ist, sind schattiert und mit Buchstaben markiert.

Abbildung 29.5
Abbildung 29.5 Tiefensuche für die große Komponente des Graphen (rekursiv).

Die erste durchlaufene Kante ist AF, was dem ersten Knoten in der ersten Adjazenzliste entspricht. Danach wird visit für den Knoten F aufgerufen, und die Kante FA wird durchlaufen, da A der erste Knoten in der Adjazenzliste von F ist. Doch A hat an dieser Stelle einen von Null verschiedenen Eintrag in val, daher nehmen wir gemäß der nächsten Eintragung in der Adjazenzliste von F die Kante FE. Dann wird EG durchlaufen, dann GE, da G und E an erster Stelle in der Liste des jeweils anderen Knotens stehen. Als nächste Kante wird GA durchlaufen; damit ist die Verarbeitung von G mittels visit abgeschlossen, und der Algorithmus fährt fort mit der Verarbeitung von E mittels visit und durchläuft EF, dann ED. Danach besteht das Besuchen von D mittels visit im Durchlaufen von DE und DF, was beides zu keinem neuen Knoten führt. Da D der letzte Knoten in der Adjazenzliste von E ist, ist das Besuchen von E mittels visit damit abgeschlossen, und das Besuchen von F wird anschließend mit dem Durchlaufen von FD vollendet. Am Schluß kehren wir zu A zurück und durchlaufen AC, CA, AB, BA und AG.

Ein anderer Weg, wie man die Vorgehensweise bei der Tiefensuche verfolgen kann, besteht darin, den Graph den rekursiven Aufrufen der Prozedur visit entsprechend nachzuzeichnen, so wie es Abbildung 29.6 zeigt. Jede zusammenhängende Komponente führt zu einem Baum, der Tiefensuchbaum für die Komponente genannt wird. Eine Preorder-Traversierung dieses Baumes liefert die Knoten des Graphen in der Reihenfolge, in der sie bei der Suche zum erstenmal angetroffen werden; eine Postorder-Traversierung des Baumes liefert die Knoten in der Reihenfolge, in der ihre Verarbeitung mittels visit vollendet wird. Beachten Sie, daß dieser Wald aus Tiefensuchbäumen einfach ein anderer Weg ist, den Graph zu zeichnen; alle Knoten und Kanten des Graphen werden durch den Algorithmus betrachtet.

Abbildung 29.6
Abbildung 29.6 Tiefensuch-Wald.

Durchgehende Linien in Abbildung 29.6 besagen, daß durch den Algorithmus festgestellt wurde, daß sich der untere Knoten in der Liste der Kanten des oberen Knotens befindet und bisher noch nicht besucht wurde, so daß ein rekursiver Aufruf erfolgte. Gestrichelte Linien entsprechen Kanten, die zu Knoten führen, die bereits besucht wurden, so daß der if-Test in visit scheiterte und die Kante nicht mittels eines rekursiven Aufrufs »verfolgt« wurde. Diese Bemerkungen beziehen sich auf das erste Mal, wo jede Kante angetroffen wird; wie wir in Abbildung 29.5 gesehen haben, verhindert der if-Test in visit auch, daß die Kante verfolgt wird, wenn sie zum zweiten Mal angetroffen wird.

Eine entscheidende Eigenschaft dieser Tiefensuchbäume für ungerichtete Graphen besteht darin, daß die gestrichelten Verbindungen immer von einem Knoten zu einem bestimmten Vorgänger im Baum verlaufen (einem anderen Knoten im gleichen Baum, der sich auf dem Pfad zur Wurzel weiter oben befindet). Zu jedem beliebigen Zeitpunkt während der Ausführung des Algorithmus lassen sich die Knoten in drei Klassen einteilen: Knoten, für die visit abgeschlossen ist, Knoten, für die visit nur teilweise abgeschlossen ist, und Knoten, die noch gar nicht betrachtet wurden. Aus der Definition von visit ergibt sich, daß wir keine Kante antreffen werden, die auf irgendeinen Knoten der ersten Klasse zeigt; falls wir eine Kante vorfinden, die auf einen Knoten der dritten Klasse zeigt, so erfolgt ein rekursiver Aufruf (so daß die Kante im Tiefensuchbaum mittels einer durchgehenden Linie dargestellt wird). Die einzigen verbleibenden Knoten sind die der zweiten Klasse. Doch dies sind genau die Knoten auf dem Pfad vom aktuellen Knoten zu der Wurzel im gleichen Baum, und eine beliebige Kante, die auf einen von ihnen zeigt, entspricht einer gestrichelten Linie im Tiefensuchbaum.

Eigenschaft 29.1 Für eine Tiefensuche in einem Graph, der mit Hilfe von Adjazenzlisten dargestellt ist, ist eine zu V + E proportionale Zeit erforderlich.

Wir setzen jeden der V Werte von val (woraus sich der Term V ergibt), und wir betrachten jede Kante zweimal (woraus sich der Term E ergibt). Es könnten (äußerst) lichte Graphen auftreten, für die E < V gilt, doch falls isolierte Knoten nicht zugelassen sind (zum Beispiel könnten sie in einer Vorverarbeitungsphase entfernt werden), ziehen wir es vor, uns die Laufzeit der Tiefensuche als linear bezüglich der Anzahl der Kanten vorzustellen. w.z.b.w.

Das gleiche Verfahren kann auf Graphen angewandt werden, die mit Hilfe von Adjazenzmatrizen dargestellt sind, indem die folgende Prozedur visit verwendet wird:

    procedure visit(k: integer);
      var t: integer;
      begin
      id:=id+1; val[k]:=id;
      for t:=1 to V do
        if a[k,t] then
          if val[t]=0 then visit(t);
      end;
Dem Durchlaufen einer Adjazenzliste entspricht nunmehr das Durchsuchen einer Zeile der Adjazenzmatrix nach true (welche Kanten entsprechen). Wie zuvor wird jede Kante, die auf einen Knoten zeigt, der vorher noch nicht betrachtet wurde, über einen rekursiven Aufruf »verfolgt«. Nun werden die Kanten, die mit jedem Knoten verbunden sind, in einer anderen Reihenfolge betrachtet, so daß wir einen anderen Tiefensuch-Wald erhalten, wie Abbildung 29.7 zeigt. Dies unterstreicht die Tatsache, daß der Tiefensuch-Wald einfach eine andere Darstellung des Graphen ist, eine Darstellung, deren spezielle Struktur sowohl vom Suchalgorithmus als auch von der benutzten internen Darstellung abhängt.

Abbildung 29.7
Abbildung 29.7 Tiefensuch-Wald
(Matrixdarstellung des Graphen).

Eigenschaft 29.2 Für die Tiefensuche in einem Graph, der mit Hilfe einer Adjazenzmatrix dargestellt ist, ist eine zu V2 proportionale Zeit erforderlich.

Der Beweis dieser Tatsache ist trivial: Jedes Bit in der Adjazenzmatrix wird geprüft. w.z.b.w.

Mit der Tiefensuche können einige grundlegende Probleme der Verarbeitung von Graphen sofort gelöst werden. Zum Beispiel beruht die Prozedur darauf, daß die zusammenhängenden Komponenten der Reihe nach gefunden werden: Die Anzahl der zusammenhängenden Komponenten ist gleich der Anzahl der Aufrufe von visit in der letzten Zeile des Programms. Die Überprüfung, ob ein Graph einen Zyklus aufweist, ist gleichfalls eine sehr einfache Modifikation des obigen Programms. Ein Graph beinhaltet dann und nur dann einen Zyklus, wenn in visit ein von Null verschiedener Eintrag in val entdeckt wird. Das heißt, wenn wir eine Kante antreffen, die auf einen Knoten zeigt, den wir bereits besucht haben, so liegt ein Zyklus vor. Äquivalent dazu ist die Tatsache, daß alle gestrichelten Verbindungen in den Tiefensuchbäumen zu Zyklen gehören.


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