Robert Sedgewick: Algorithmen

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


31. Gewichtete Graphen



Prioritätssuche

Wir erinnern daran, daß die Suche in Graphen gemäß Kapitel 29 mit Hilfe einer Einteilung der Knoten in drei Mengen beschrieben werden kann: Baumknoten, bei denen alle Kanten untersucht worden sind, Randknoten, die sich in einer Datenstruktur befinden, die auf ihre Verarbeitung wartet, und unsichtbare Knoten, die noch gar nicht berührt worden sind. Das grundlegende Verfahren der Suche in Graphen, das wir verwenden, beruht auf dem Schritt »bewege einen Knoten (der mit x bezeichnet werde) vom Rand zum Baum, und nimm dann alle unsichtbaren Knoten, die zu x benachbart sind, in den Rand auf«. Wir benutzen den Begriff Prioritätssuche, um die allgemeine Strategie zu bezeichnen, die darin besteht, eine Prioritätswarteschlange zu benutzen, um zu entscheiden, welcher Knoten vom Rand zu nehmen ist. Dies ermöglicht eine hohe Flexibilität. Wie wir sehen werden, unterscheiden sich verschiedene klassische Algorithmen (einschließlich Tiefen- und Breitensuche) nur hinsichtlich der Wahl der Priorität.

Abbildung 31.4
Abbildung 31.4 Inhalt der Prioritätswarteschlange während der Erzeugung des minimalen Spannbaumes.

Für die Berechnung des minimalen Spannbaumes sollte die Priorität jedes zum Rand gehörenden Knotens die Länge der kürzesten Kante sein, die ihn mit dem Baum verbindet. Abbildung 31.4 zeigt den Inhalt der Prioritätswarteschlange während des Erzeugungsprozesses, den die Abbildungen 31.3 und 31.5 veranschaulichen. Aus Gründen der Übersichtlichkeit wurden die Elemente in der Warteschlange in sortierter Reihenfolge dargestellt. Diese Implementation von Prioritätswarteschlangen mittels »sortierter Listen« könnte für kleine Graphen geeignet sein, doch für umfangreiche Graphen sollten Heaps verwendet werden, um zu gewährleisten, daß alle Operationen in O(log N) Schritten ausgeführt werden können (siehe Kapitel 11).

Abbildung 31.5
Abbildung 31.5 Vollendung der Erzeugung des minimalen Spannbaumes.

Zuerst betrachten wir lichte Graphen mit einer Adjazenzlisten-Darstellung. Wie bereits erwähnt, fügen wir zu dem Datensatz der Kante ein Feld w für das Gewicht hinzu (und modifizieren das Eingabeprogramm dahingehend, daß auch Gewichte eingelesen werden). Dann erhalten wir, unter Verwendung einer Prioritätswarteschlange für den Rand, die folgende Implementation:

    procedure listpfs;
      var id,k: integer;
          val: array[1..maxV] of integer;
      procedure visit(k: integer);
        var t: link;
        begin
        if pqupdate(k,unseen) then dad[k]:=0;
        repeat
          id:=id+1; 
          k:=pqremove; val[k]:=-val[k];
          if val[k]=unseen then val[k]:=0;
          t:=adj[k];
          while t<>z do
            begin
            if val[t^.v]<0 then 
              if pqupdate(t^.v,priority) then 
                begin val[t^.v]:=-(priority); dad[t^.v]:=k end;
            t:=t^.next
            end
        until pqempty
        end;
      begin
      id:=0; pqinitialize;
      for k:=1 to V do val[k]:=-unseen;
      for k:=1 to V do
        if val[k]=-unseen then visit(k)
      end;

Um den minimalen Spannbaum zu berechnen, ist priority an beiden Stellen durch t^.w zu ersetzen. Die Prozeduren pqinitialize und pqremove sind Hilfsprozeduren für Prioritätswarteschlangen, wie sie in Kapitel 11 beschrieben wurden. Die Funktion pqupdate ist eine leicht zu implementierende Ergänzung zu dieser Menge von Hilfsprogrammen, deren Zweck darin besteht zu gewährleisten, daß der übergebene Knoten höchstens mit der angegebenen Priorität in der Warteschlange erscheint: Falls sich der Knoten nicht in der Warteschlange befindet, wird pqinsert ausgeführt, und falls der Knoten vorhanden ist, jedoch eine höhere Priorität besitzt, wird pqchange verwendet, um die Priorität zu ändern. Falls irgendeine Änderung vorgenommen wurde (entweder Einfügung oder Änderung der Priorität), gibt pqupdate den Wert true zurück. Dies gibt dem obigen Programm die Möglichkeit, die Felder val und dad zu aktualisieren. Das Feld val selbst könnte die Prioritätswarteschlange in Wirklichkeit auf «indirekte« Weise enthalten; im obigen Programm haben wir die Operationen mit der Prioritätswarteschlange der Klarheit wegen herausgelöst.

Abgesehen von der Umänderung der Datenstruktur in eine Prioritätswarteschlange ist dies praktisch das gleiche Programm, das wir für Tiefen- und Breitensuche verwendeten, mit zwei Ausnahmen. Erstens sind zusätzliche Maßnahmen erforderlich, wenn eine Kante angetroffen wird, die bereits dem Rand angehört. Bei Tiefen- und Breitensuche werden solche Kanten ignoriert, doch im obigen Programm müssen wir prüfen, ob die neue Kante die Priorität verringert. Dadurch wird gewährleistet, daß wir als nächstes immer denjenigen Knoten des Randes besuchen, der dem Baum am nächsten liegt. Zweitens erfolgt dieses Programm explizit der Erzeugung des Baumes, indem das Feld dad geführt wird, in welchem der Vorgänger jedes Knotens im Prioritätssuchbaum gespeichert wird (der Name des Knotens, der bewirkt hat, daß er vom Rand zum Baum bewegt wurde). Außerdem ist für jeden Knoten k im Baum val[k] das Gewicht der Kante zwischen k und dad[k]. Randknoten sind wie zuvor durch negative Werte von val markiert; unsichtbare Knoten sind mittels der Marke -unseen anstelle von 0 markiert. Der Grund für diese Änderung wird weiter unten klar werden.

Abbildung 31.6
Abbildung 31.6 Erzeugung eines umfangreichen minimalen Spannbaumes.

Abbildung 31.5 vervollständigt die Konstruktion des minimalen Spannbaumes für unser Beispiel. Wie üblich sind Knoten des Randes durch Quadrate mit Buchstaben dargestellt, Baumknoten durch Kreise mit Buchstaben und unsichtbare Knoten durch Kreise ohne Buchstaben. Kanten des Baumes sind als fette schwarze Linien gezeichnet, und für jeden Knoten des Randes ist die kürzeste Kante, die ihn mit dem Baum verbindet, schattiert. Dem Leser wird empfohlen, die Erzeugung des Baumes unter Benutzung dieser Skizzen und der Abbildung 31.4 zu verfolgen. Man beachte insbesondere, wie Knoten G zum Baum hinzugefügt wird, nachdem er während mehrerer Schritte dem Rand angehörte. Am Anfang beträgt der Abstand von G zum Baum 6 (wegen der Kante GA). Nachdem L zum Baum hinzugefügt worden ist, verringert GL den Abstand auf 5, und danach, nach dem Hinzufügen von E, verkürzt sich der Abstand schließlich auf 1, und G wird vor J zum Baum hinzugefügt. Abbildung 31.6 zeigt die Erzeugung eines minimalen Spannbaumes für unseren großen »Labyrinth«-Graph, wobei die Längen der Kanten als Gewichte benutzt werden.

Eigenschaft 31.2 Prioritätssuche bei lichten Graphen ermöglicht die Berechnung des minimalen Spannbaumes in O((E + V) log V) Schritten.

Die obige Eigenschaft 31.1 kommt zur Anwendung: Die beiden besagten Knotenmengen sind die besuchten Knoten und die noch nicht besuchten Knoten. Bei jedem Schritt wählen wir die kürzeste Kante von einem besuchten Knoten zu einem Randknoten aus (es gibt keine Kanten von besuchten Knoten zu unsichtbaren Knoten). Daher gehört gemäß Eigenschaft 31.1 jede Kante, die ausgewählt wird, zum minimalen Spannbaum. Die Prioritätswarteschlange enthält nur Knoten; bei einer Implementation als Heap (siehe Kapitel 11) erfordert dann jede Operation O(log V) Schritte. Jeder Knoten führt zu einer Einfügung, und jede Kante führt zu einer pqchange-Operation. w.z.b.w.

Weiter unten werden wir sehen, daß mit diesem Verfahren bei einer geeigneten Wahl der Priorität auch das Problem des kürzesten Pfades gelöst werden kann. Außerdem sehen wir, wie eine andere Implementation der Prioritätswarteschlange einen Algorithmus mit einer zu V2 proportionalen Laufzeit ergeben kann, der für dichte Graphen geeignet ist. Dieser ist zu einem seit langem bekannten Algorithmus äquivalent, der spätenstens aus dem Jahr 1957 stammt; für minimale Spannbäume wird er im allgemeinen R. Prim zugeschrieben, für kürzeste Pfade im allgemeinen E. Dijkstra. Der Einheitlichkeit wegen wollen wir diese Lösungen (für dichte Graphen) als »Algorithmus von Prim« bzw. »Algorithmus von Dijkstra« bezeichnen; das obige Verfahren (für lichte Graphen) nennen wir die »Lösung mit Prioritätssuche«.

Die Prioritätssuche ist eine echte Verallgemeinerung der Breiten- und Tiefensuche, da diese Verfahren durch geeignete Festlegungen der Priorität abgeleitet werden können. Wir erinnern daran, daß sich id während der Ausführung des Algorithmus von 1 auf V erhöht und demzufolge benutzt werden kann, um den Knoten eindeutige Prioritäten zuzuordnen. Wenn wir in listpfs an den beiden Stellen, wo priority auftritt, dieses durch V-id ersetzen, erhalten wir Tiefensuche, da neu gefundene Knoten die höchste Priorität haben. Wenn wir id als priority benutzen, erhalten wir Breitensuche, da alte Knoten die höchste Priorität haben. Diese Festlegungen der Priorität bewirken, daß sich Prioritätswarteschlangen wie Stapel und Warteschlangen verhalten.


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