Robert Sedgewick: Algorithmen

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


29. Elementare Algorithmen für Graphen



Nichtrekursive Tiefensuche

Tiefensuche in einem Graph ist eine Verallgemeinerung der Traversierung eines Baumes. Wenn es auf einen Baum angewandt wird, ist sie zur Traversierung des Baumes genau äquivalent; für Graphen entspricht es der Traversierung eines Baumes, der den Graph »aufspannt« und der »entdeckt« wird, während der Prozeß des Suchens voranschreitet. Wie wir gesehen haben, hängt der spezielle durchlaufene Baum davon ab, wie der Graph dargestellt ist.

Die Rekursion bei der Tiefensuche kann durch Verwendung eines Stapels beseitigt werden, in der gleichen Weise, wie wir in Kapitel 5 die Rekursion aus der Traversierung von Bäumen beseitigt haben. Für Bäume stellten wir fest, daß uns die Beseitigung der Rekursion zu einer anderen (recht einfachen) äquivalenten Implementation führte, und wir fanden einen zugehörigen nichtrekursiven Algorithmus für die Traversierung (Level-Order). Für Graphen wird die Entwicklung ähnlich verlaufen und letzten Endes (in Kapitel 31) zu einem Mehrzweck-Algorithmus für die Traversierung von Graphen führen.

Auf unserer Erfahrung aus dem Kapitel 5 aufbauend gehen wir unmittelbar zu einer Implementation auf der Basis eines Stapels über:

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

Knoten, die berührt, aber noch nicht besucht worden sind, werden in einem Stapel gespeichert. Um einen Knoten zu besuchen, durchlaufen wir seine Kanten und legen jeden Knoten im Stapel ab, der noch nicht besucht worden ist und sich nicht bereits im Stapel befindet. Bei der rekursiven Implementation ist die Verwaltung für die »teilweise besuchten« Knoten in der lokalen Variablen t der rekursiven Prozedur versteckt. Wir könnten dies direkt implementieren, indem wir auf die Adjazenzlisten weisende (t entsprechende) Zeiger verwenden usw. Stattdessen erweitern wir einfach die Bedeutung der Einträge von val, um Knoten markieren zu helfen, die sich im Stapel befinden: Knoten mit Einträgen 0 in val sind (wie zuvor) noch nicht angetroffen worden, solche mit negativen Einträgen in val befinden sich im Stapel, und solche mit positiven Einträgen in val sind bereits besucht worden (alle Kanten in ihren Adjazenzlisten sind im Stapel abgelegt worden).

Abbildung 29.8
Abbildung 29.8 Beginn der Stapel-basierten Suche.

Abbildung 29.8 veranschaulicht die Arbeitsweise dieser auf einem Stapel beruhenden Tiefensuchprozedur, während die ersten vier Knoten aus unserem Graphen besucht werden. Jede Skizze in dieser Abbildung entspricht einem Besuch eines Knotens: Der besuchte Knoten ist durch ein Quadrat gekennzeichnet, und alle Kanten in seiner Adjazenzliste sind schattiert. Wie zuvor sind Knoten, die noch nicht angetroffen wurden, mit keinem Buchstaben markiert und schattiert, und Knoten, für die das Besuchen beendet ist, sind mit einem Buchstaben markiert und nicht schattiert; weiterhin ist jeder Knoten durch eine fette Linie mit dem Knoten verbunden, der sein Ablegen im Stapel bewirkte. Knoten, die sich noch im Stapel befinden, sind durch Quadrate gekennzeichnet.

Abbildung 29.9
Abbildung 29.9 Inhalt des Stapels während der Stapel-basierten Suche.

Der erste besuchte Knoten ist A; die Kanten AF, AB, AC und AG werden durchlaufen, und F, B, C und G werden im Stapel abgelegt. Dann wird G entnommen (beachten Sie, daß es der letzte Knoten in der Adjazenzliste von A ist), und die Kanten GA und GE werden durchlaufen, was zur Folge hat, daß E im Stapel abgelegt wird (A wird nicht nochmals abgelegt). Danach werden EG, EF und ED durchlaufen, und D wird im Stapel abgelegt usw. Abbildung 29.9 zeigt den Inhalt des Stapels während der Suche, und Abbildung 29.10 zeigt die Fortsetzung zu Abbildung 29.8.

Abbildung 29.10
Abbildung 29.10 Vollendung der Stapel-basierten Suche.

Der Leser hat zweifellos bemerkt, daß das obige Programm die Kanten und Knoten nicht in genau der gleichen Reihenfolge besucht wie die rekursive Implementation. Das ließe sich erreichen, indem man die Kanten in umgekehrter Reihenfolge im Stapel ablegt und den Fall, wo ein bereits im Stapel befindlicher Knoten erneut angetroffen wird, anders behandelt. Wenn wir die Kanten in der Adjazenzliste für jeden Knoten in der umgekehrten Reihenfolge, wie sie in der Liste erscheinen, im Stapel ablegen würden, würden wir die entsprechenden Knoten in der gleichen Reihenfolge entnehmen und besuchen wie bei der rekursiven Implementation. (Dies ist der gleiche Effekt wie in dem Beispiel der Traversierung von Bäumen in Kapitel 5, wo bei der nichtrekursiven Implementation der rechte Teilbaum vor dem linken im Stapel abgelegt wird.) Ein noch grundlegenderer Unterschied besteht darin, daß das auf dem Stapel beruhende Verfahren technisch überhaupt keine Tiefensuchprozedur ist, da der Knoten besucht wird, der zuletzt im Stapel abgelegt wurde, und nicht, wie bei der rekursiven Tiefensuche, der Knoten, der als letzter angetroffen wurde. Hier läßt sich Abhilfe schaffen, indem man im Stapel befindliche Knoten an das obere Ende des Stapels bewegt, wenn sie erneut angetroffen werden, doch erfordert diese Operation eine leistungsfähigere Datenstruktur als einen Stapel. Eine sehr einfache Methode, um dies zu implementieren, betrachten wir in Kapitel 31.


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