Robert Sedgewick: Algorithmen

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


29. Elementare Algorithmen für Graphen



Breitensuche

Genauso wie bei der Traversierung von Bäumen (siehe Kapitel 4) können wir als Datenstruktur für die Speicherung der Knoten anstelle eines Stapels eine Warteschlange benutzen. Dies führt zu einem zweiten klassischen Algorithmus für die Traversierung von Graphen, der Breitensuche genannt wird. Um die Breitensuche zu implementieren, tauschen wir in dem obigen Suchprogramm Stapel-Operationen gegen Warteschlangen-Operationen aus:

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

Diese Veränderung der Datenstruktur beeinflußt die Reihenfolge, in der die Knoten besucht werden. Für den Graph aus unserem kleinen Beispiel werden die Kanten in der Reihenfolge AF AC AB AG FA FE FD CA BA GE GA DF DE EG EF ED HI IH JK JL JM KJ LJ LM MJ ML besucht. Abbildung 29.11 zeigt den Inhalt der Warteschlange während der Traversierung.

Abbildung 29.11
Abbildung 29.11 Inhalt der Warteschlange während der Breitensuche.

Wie bei der Tiefensuche können wir aus den Kanten, die uns zum erstenmal zu jedem Knoten führen, einen Wald definieren, wie es in Abbildung 29.12 dargestellt ist. Breitensuche entspricht einer Level-Order-Traversierung der Bäume in diesem Wald.

Abbildung 29.12
Abbildung 29.12 Breitensuch-Wald.

Bei beiden Algorithmen können wir uns die Knoten als in drei Klassen eingeteilt vorstellen: Baumknoten (oder besuchte Knoten), welche aus der Datenstruktur entnommen worden sind; Randknoten, die Baumknoten benachbart, jedoch noch nicht besucht worden sind; sowie unsichtbare Knoten, die überhaupt noch nicht angetroffen worden sind. Falls jeder Baumknoten mit der Kante verbunden wird, die bewirkt hat, daß er zur Datenstruktur hinzugefügt wurde (fett gezeichnete Kanten in den Abbildungen 29.8 und 29.10), so bilden diese Kanten einen Baum.

Um eine zusammenhängende Komponente eines Graphen systematisch abzusuchen (eine Prozedur visit zu implementieren), beginnen wir mit einem Knoten am Rand, während alle anderen unsichtbar sind, und führen den folgenden Schritt so oft aus, bis alle Knoten besucht worden sind: »Bewege einen Knoten (sagen wir x) vom Rand zum Baum, und nehme alle dem Knoten x benachbarten unsichtbaren Knoten in den Rand auf.« Verfahren zur Traversierung von Graphen unterscheiden sich darin, wie entschieden wird, welcher Knoten vom Rand zum Baum bewegt werden soll. Bei der Tiefensuche möchten wir den Knoten aus dem Rand auswählen, der als letzter angetroffen wurde; dies entspricht der Verwendung eines Stapels zum Speichern der Knoten, die zum Rand gehören. Bei der Breitensuche möchten wir den Knoten aus dem Rand auswählen, dessen Antreffen am weitesten zurückliegt; dies entspricht der Verwendung einer Warteschlange zum Speichern der zum Rand gehörenden Knoten. In Kapitel 31 werden wir die Auswirkung der Verwendung einer Prioritätswarteschlange für den Rand untersuchen.

Abbildung 29.13
Abbildung 29.13 Tiefensuche in einem größeren Graph.

Der Gegensatz zwischen Tiefensuche und Breitensuche wird sehr deutlich sichtbar, wenn wir einen umfangreicheren Graph betrachten. Abbildung 29.13 zeigt die Arbeitsweise der Tiefensuche in einem größeren Graph nach einem Drittel und nach zwei Dritteln des Weges durch den Prozeß; Abbildung 29.14 ist das entsprechende Bild für die Breitensuche. In diesen Skizzen sind Knoten und Kanten im Baum schwarz dargestellt, unsichtbare Knoten sind schattiert, und Randknoten sind weiß.

Abbildung 29.14
Abbildung 29.14 Breitensuche in einem größeren Graph.

In beiden Fällen beginnt die Suche bei dem linken unteren Knoten. Bei der Tiefensuche windet sich der Weg durch den Graph hindurch, wobei im Stapel die Stellen gespeichert werden, wo andere Pfade abzweigen; bei der Breitensuche wird der Graph unter Benutzung einer Warteschlange zur Speicherung der Front der besuchten Stellen »durchkämmt«. Bei der Tiefensuche wird der Graph »erkundet«, indem nach neuen Knoten weit weg vom Ausgangspunkt gesucht wird und näherliegende Knoten nur dann genommen werden, wenn Sackgassen gefunden wurden; bei der Breitensuche wird das Gebiet in der Nähe des Ausgangspunktes vollständig abgesucht, und die Suche führt erst dann weiter weg, wenn alles in der Nähe liegende betrachtet worden ist. Auch hier hängt die Reihenfolge, in der die Knoten besucht werden, in starkem Maße von der Reihenfolge ab, in der die Kanten bei der Eingabe erscheinen, sowie von den Auswirkungen dieser Reihenfolge auf die Reihenfolge, in der Knoten in den Adjazenzlisten erscheinen.

Abgesehen von diesen Unterschieden in der Arbeitsweise ist es interessant, über die grundlegenden Unterschiede zwischen den Implementationen dieser Verfahren nachzudenken. Tiefensuche läßt sich sehr einfach rekursiv ausdrücken (da die ihm zugrundeliegende Datenstruktur ein Stapel ist), und Breitensuche ermöglicht eine sehr einfache nichtrekursive Implementation (da die ihm zugrundeliegende Datenstruktur eine Warteschlange ist). In Kapitel 31 sehen wir, daß die wirklich zugrundeliegende Datenstruktur für Graphen-Algorithmen eine Prioritätswarteschlange ist, und dies hat eine große Vielfalt interessanter Eigenschaften und Algorithmen zur Folge.


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