Robert Sedgewick: Algorithmen

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


31. Gewichtete Graphen



Minimaler Spannbaum und kürzeste Pfade in dichten Graphen

Für einen mit Hilfe einer Adjazenzmatrix dargestellten Graph ist es am besten, für die Prioritätswarteschlange eine Darstellung als ungeordnetes Feld zu benutzen, um für jeden Algorithmus für die Traversierung eines Graphen mit Prioritätssuche eine zu V2 proportionale Laufzeit zu erreichen. Dies wird realisiert, indem die Schleife zur Aktualisierung der Prioritäten und die Schleife zur Bestimmung des Minimums kombiniert werden: Jedesmal, wenn wir einen Knoten vom Rand entfernen, durchlaufen wir alle Knoten, wobei wir bei Bedarf ihre Priorität aktualisieren und den gefundenen minimalen Wert registrieren. Dies liefert einen linearen Algorithmus für die Prioritätssuche (und folglich für die Probleme des minimalen Spannbaumes und des kürzesten Pfades) für dichte Graphen.

Wir speichern die Prioritätswarteschlange im Feld val (dies könnte auch in listpfs erfolgen, wie oben erörtert wurde), doch anstatt Heaps zu verwenden, implementieren wir die Prioritätswarteschlangenoperation unmittelbar. Wie oben gibt das Vorzeichen eines Eintrags in val an, ob der entsprechende Knoten dem Baum oder der Prioritätswarteschlange angehört. Alle Knoten beginnen in der Prioritätswarteschlange und haben die als Marke dienende Priorität unseen (unsichtbar). Um die Priorität eines Knotens zu ändern, weisen wir einfach dem Eintrag in val für diesen Knoten die neue Priorität zu. Um den Knoten mit der höchsten Priorität zu entfernen, durchsuchen wir das Feld val, um den Knoten mit dem größten negativen (am nächsten bei 0 gelegenen) Wert in val zu finden, und kehren dann bei seiner Eintragung in val das Vorzeichen um. Nachdem wir in dem von uns verwendeten Programm listpfs diese mechanischen Änderungen vorgenommen haben, erhalten wir das folgende kompakte Programm:

    procedure matrixpfs;
      var k,min,t: integer;
      begin
      for k:=1 to V do
        begin val[k]:=-unseen; dad[k]:=0 end;
      val[0]:=-(unseen+1);
      min:=1;
      repeat
        k:=min; val[k]:=-val[k]; min:=0;
        if val[k]=unseen then val[k]:=0;
        for t:=1 to V do
          if val[t]<0 then
            begin
            if (a[k,t]<>0) and (val[t]<-(priority) then
              begin val[t]:=-(priority); dad[t]:=k end;
            if val[t]>val[min] then min:=t;
            end
      until min=0;
      end;

Beachten Sie, daß unseen etwas kleiner als maxint sein muß, da unseen +1 als Marke für das Auffinden des Minimums verwendet wird und dieser Wert mit negativem Vorzeichen darstellbar sein muß.

Wenn wir die Gewichte in der Adjazenzmatrix speichern und anstelle von priority in diesem Programm a[k,t] benutzen, erhalten wir den Algorithmus von Prim zur Bestimmung des minimalen Spannbaumes; wenn wir anstelle von priority val[k]+a[k,t] benutzen, erhalten wir den Algorithmus von Dijkstra für das Problem des kürzesten Pfades. Wie oben erhalten wir, wenn wir den Programmabschnitt zur Registrierung von id als Anzahl der bisher durchsuchten Knoten einfügen und V-id anstelle von priority verwenden, die Tiefensuche; wenn wir id verwenden, erhalten wir die Breitensuche. Dieses Programm unterscheidet sich von dem Programm für die Prioritätssuche, mit dem wir bei lichten Graphen gearbeitet haben, nur hinsichtlich der verwendeten Darstellung des Graphen (Adjazenzmatrix anstelle einer Adjazenzliste) und der Implementation der Prioritätswarteschlange (ungeordnetes Feld anstelle eines indirekten Heap).

Eigenschaft 31.5 Die Probleme des minimalen Spannbaumes und des kürzesten Pfades können für dichte Graphen in linearer Zeit gelöst werden.

Aus der Betrachtung des Programms ist unmittelbar ersichtlich, daß die Laufzeit im ungünstigsten Fall proportional zu V2 ist. Jedesmal, wenn ein Knoten besucht wird, erfüllt ein Durchlaufen der V Einträge in seiner Zeile in der Adjazenzmatrix den dualen Zweck der Prüfung aller benachbarten Kanten und der Aktualisierung und des Auffindens des nächsten minimalen Wertes in der Prioritätswarteschlange. Daher ist die Laufzeit linear, wenn E zu V2 proportional ist. w.z.b.w.

Wir haben drei Programme für das Problem des minimalen Spannbaumes mit sehr unterschiedlichen Verhaltensmerkmalen betrachtet: das Verfahren der Prioritätssuche, den Algorithmus von Kruskal und den Algorithmus von Prim (s.o.). Für manche Graphen dürfte der Algorithmus von Prim der schnellste der drei Algorithmen sein, für andere der Algorithmus von Kruskal, für wieder andere die Prioritätssuche. Wie oben beschrieben, ist der ungünstigste Fall für die Prioritätssuche (E + V) log V, während der ungünstigste Fall für den Algorithmus von Prim V2 und für den Algorithmus von Kruskal E log E ist. Doch es wäre unklug, die Auswahl unter den Algorithmen allein auf der Grundlage dieser Formeln zu treffen, da das Auftreten von Graphen, die dem ungünstigsten Fall entsprechen, in der Praxis unwahrscheinlich ist. In Wirklichkeit dürften sowohl die Prioritätssuche als auch das Verfahren von Kruskal für Graphen, die in der Praxis auftreten, in einer zu E proportionalen Zeit ablaufen: das erstere, weil die meisten Kanten keine Anpassung der Prioritätswarteschlange erfordern, die log V Schritte benötigt, und das letztere, weil die längste Kante im minimalen Spannbaum wahrscheinlich relativ kurz ist, so daß der Prioritätswarteschlange nicht viele Kanten entnommen werden. Bei lichten Graphen läuft wahrscheinlich die Prioritätssuche am schnellsten ab, da sie mit einer kleinen Prioritätswarteschlange arbeiten dürfte. Natürlich läuft das Verfahren von Prim für dichte Graphen gleichfalls in einer ungefähr zu E proportionalen Zeit ab (doch es sollte nicht für lichte Graphen benutzt werden).


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