Robert Sedgewick: Algorithmen

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


31. Gewichtete Graphen



Das Verfahren von Kruskal

Eine vollständig andere Vorgehensweise zur Bestimmung des minimalen Spannbaumes besteht darin, einfach Kanten nacheinander hinzuzufügen und hierbei bei jedem Schritt die kürzeste Kante zu verwenden, die keinen Zyklus bildet. Anders ausgedrückt, der Algorithmus beginnt mit einem aus N Bäumen bestehenden Wald; in N Schritten kombiniert er jeweils zwei Bäume (unter Verwendung der kürzesten möglichen Kante), bis nur noch ein Baum übrigbleibt. Dieser Algorithmus ist spätestens seit 1956 bekannt und wird im allgemeinen J. Kruskal zugeschrieben.

Abbildung 31.7
Abbildung 31.7 Anfangsschritte des Algorithmus von Kruskal.

Die Abbildungen 31.7 und 31.8 zeigen die Arbeitsweise dieses Algorithmus für den Graph aus unserem Beispiel. Die ersten ausgewählten Kanten sind die mit der kleinsten Länge (1) im Graph. Danach werden Kanten mit der Länge 2 ausprobiert; beachten Sie insbesondere, daß FE betrachtet, jedoch nicht aufgenommen wird, da diese Kante mit bereits zum Baum gehörenden Kanten einen Zyklus bildet. Die nicht zusammenhängenden Komponenten entwickeln sich nach und nach zu einem Baum, im Gegensatz zur Prioritätssuche, bei der der Baum jedesmal um eine Kante wächst.

Abbildung 31.8
Abbildung 31.8 Vollendung des Algorithmus von Kruskal.

Die Implementation des Algorithmus von Kruskal kann aus Programmen zusammengesetzt werden, die wir bereits untersucht haben. Erstens müssen wir die Kanten entsprechend der wachsenden Reihenfolge ihres Gewichts nacheinander betrachten. Eine Möglichkeit wäre, sie einfach zu sortieren, doch es erweist sich als günstiger, eine Prioritätswarteschlange zu benutzen, vor allem weil wir vielleicht nicht alle Kanten betrachten müssen. Dies wird weiter unten ausführlicher erörtert. Zweitens müssen wir in der Lage sein zu prüfen, ob eine gegebene Kante einen Zyklus erzeugt, wenn sie zu den bisher verwendeten Kanten hinzugefügt wird. Die im vorangegangenen Kapitel untersuchten Strukturen für die Vereinigungs-Suche sind für diese Aufgabe prädestiniert.

Nunmehr ist die geeignete Datenstruktur für den Graph einfach ein Feld edges mit einer Eintragung für jede Kante. Dieses Feld könnte mittels Tiefensuche oder einer einfacheren Prozedur leicht aus der Adjazenzlisten- oder Adjazenzmatrixdarstellung gewonnen werden. Im nachfolgenden Programm füllen wir dieses Feld jedoch direkt mit Hilfe der Eingabedaten. Die Prozeduren für indirekte Prioritätswarteschlangen pqconstruct und pqremove aus Kapitel 11 werden benutzt, um die Prioritätswarteschlange zu aktualisieren, wobei die Felder mit der Angabe des Gewichts (w) im Feld edge für die Prioritäten verwendet werden. Die Prozeduren findinit und find aus Kapitel 30 werden für den Test auf das Vorhandensein von Kreisen angewandt. Das Programm ruft einfach die Prozedur edgefound für jede Kante im Spannbaum auf; mit etwas mehr Aufwand könnte ein Feld dad oder eine andere Darstellung berechnet werden.

    program kruskal(input,output);
      const maxV=50; maxE=2500;
      type  edge=record v1,v2,w: integer end;
      var i,j,m,x,y,V,E: integer;
          edges: array[0..maxE] of edge;
      begin
      readln(V,E);
      for j:=1 to E do
        begin
        readln(c,d,edges[j].w);
        edges[j].v1:=index(c);
        edges[j].v2:=index(d);
        end;
      findinit; pqconstruct; i:=0;
      repeat
        m:=pqremove; x:=edges[m].v1; y:=edges[m].v2;
        if find(x,y,true) then
          begin
          edgefound(x,y);
          i:=i+1
          end
      until pqempty or (i=V-1);
      end.

Wir bemerken, daß es zwei Möglichkeiten gibt, wie der Prozeß beendet werden kann. Falls wir V - 1 Kanten finden, so liegt ein Baum vor, und wir können abbrechen. Falls die Prioritätswarteschlange schon vorher geleert wird, so haben wir alle Kanten betrachtet, ohne einen Spannbaum zu finden; dieser Fall tritt ein, wenn der Graph nicht zusammenhängend ist. Die Laufzeit dieses Programms wird primär durch die Zeit bestimmt, die für die Verarbeitung der Kanten in der Prioritätswarteschlange benötigt wird.

Eigenschaft 31.3 Mit dem Algorithmus von Kruskal wird der minimale Spannbaum eines Graphen in O(E log E) Schritten berechnet.

Die Korrektheit dieses Algorithmus folgt auch aus Eigenschaft 31.1. Die beiden besagten Knotenmengen sind die Knoten, die zu für den Baum ausgewählten Kanten gehören, und die noch nicht berührten Knoten. Jede hinzugefügte Kante ist die kürzeste Kante zwischen Knoten in diesen beiden Mengen. Der ungünstigste Fall ist ein Graph, der nicht zusammenhängend ist, so daß alle Kanten untersucht werden müssen. Selbst für einen zusammenhängenden Graph ist der ungünstigste Fall der gleiche, da der Graph aus zwei Anhäufungen von Knoten bestehen könnte, die alle durch sehr kurze Kanten miteinander verbunden sind, mit nur einer sehr langen Kante, die die zwei Anhäufungen verbindet. Dann gehört die längste Kante im Graph zum minimalen Spannbaum, doch sie ist die letzte Kante, die der Prioritätswarteschlange entnommen wird. Bei typischen Graphen können wir damit rechnen, daß der Spannbaum vollständig ist (er hat nur V - 1 Kanten), lange bevor die längste Kante im Graph an die Reihe kommt, doch es wird stets eine zu E proportionale Zeit benötigt, um am Anfang die Prioritätswarteschlange zu erzeugen (siehe Eigenschaft 11.2). w.z.b.w.

Abbildung 31.9 zeigt die Erzeugung eines umfangreicheren minimalen Spannbaumes mit Hilfe des Algorithmus von Kruskal. Diese Skizze zeigt deutlich, wie bei diesem Verfahren alle kurzen Kanten zuerst ausgewählt werden; die längeren (diagonalen) Kanten werden zuletzt hinzugefügt.

Abbildung 31.9
Abbildung 31.9 Bestimmung eines umfangreichen minimalen Spannbaumes mit dem Algorithmus von Kruskal.

Anstatt Prioritätswarteschlangen zu verwenden, könnte man die Kanten einfach am Anfang dem Gewicht nach sortieren und sie dann der Reihe nach verarbeiten. Weiterhin kann die Prüfung auf das Vorliegen eines Zyklus in einer zu E log E proportionalen Zeit mit einer Strategie ausgeführt werden, die viel einfacher ist als Vereinigungs-Suche, was einen Algorithmus für den minimalen Spannbaum ergibt, der stets E log E Schritte benötigt. Dies ist das ursprünglich von Kruskal vorgeschlagene Verfahren, doch wir bezeichnen die obige modernisierte Variante, bei der Prioritätswarteschlangen und Strukturen der Vereinigungs-Suche benutzt werden, als »Algorithmus von Kruskal«.


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