Robert Sedgewick: Algorithmen

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


31. Gewichtete Graphen



Minimaler Spannbaum

Ein minimaler Spannbaum eines gewichteten Graphen ist eine Menge von Kanten, die alle Knoten so verbindet, daß die Summe der Kantengewichte wenigstens ebenso klein ist wie die Summe der Gewichte jeder beliebigen anderen Menge von Kanten, die alle Knoten verbinden. Der minimale Spannbaum muß nicht eindeutig sein: Abbildung 31.2 zeigt drei minimale Spannbäume für den Graph aus unserem Beispiel. Es läßt sich leicht beweisen, daß die »Menge von Kanten« in der obigen Definition einen Spannbaum bilden muß: Wenn ein Zyklus enthalten ist, kann eine bestimmte Kante in dem Kreis gelöscht werden, was eine Menge von Kanten ergibt, die noch immer alle Knoten verbindet, jedoch ein kleineres Gewicht hat.

Abbildung 31.2
Abbildung 31.2 Minimale Spannbäume.

Wir haben in Kapitel 29 gesehen, daß in vielen Prozeduren für die Traversierung von Graphen ein Spannbaum für den Graph berechnet wird. Wie können wir es für einen gewichteten Graph so einrichten, daß der berechnete Baum derjenige ist, der das kleinste Gesamtgewicht hat? Es gibt verschiedene Wege, das zu erreichen, die alle auf der folgenden allgemeinen Eigenschaft minimaler Spannbäume beruhen.

Eigenschaft 31.1 Für jede gegebene Zerlegung eines Graphen in zwei Mengen enthält der minimale Spannbaum die kürzeste der Kanten, die Knoten aus der einen Menge mit denen der anderen verbinden.

Wenn wir zum Beispiel die Knoten des Graphen aus unserem Beispiel in die Mengen {A B C D} und {E F G H I J K L M} zerlegen, so folgt daraus, daß DF jedem minimalen Spannbaum angehören muß. Diese Eigenschaft läßt sich leicht indirekt beweisen. Bezeichnen wir die kürzeste Kante, die die zwei Mengen verbindet, mit s, und nehmen wir an, daß s nicht im minimalen Spannbaum enthalten ist. Betrachten wir dann den Graph, der gebildet wird, indem s zu dem besagten minimalen Spannbaum hinzugefügt wird. Dieser Graph besitzt einen Zyklus; in diesem Zyklus muß neben s noch eine weitere Kante die beiden Mengen verbinden. Das Löschen dieser Kante und das Hinzufügen von s ergibt einen kürzeren Spannbaum, und dies widerspricht der Annahme, daß s nicht im minimalen Spannbaum enthalten ist. w.z.b.w.

Folglich können wir den minimalen Spannbaum erzeugen, indem wir bei einem beliebigen Knoten beginnen und als nächstes immer den Knoten nehmen, der den bereits verwendeten Knoten »am nächsten« liegt. Mit anderen Worten, wir suchen unter jenen Kanten, die bereits im Baum befindliche Knoten mit noch nicht im Baum enthaltenen Knoten verbinden, die Kante mit dem kleinsten Gewicht und fügen dann diese Kante und den Knoten, zu dem sie führt, zum Baum hinzu. (Falls es mehrere Kanten mit diesem kleinsten Gewicht gibt, kann jede beliebige dieser Kanten gewählt werden.) Eigenschaft 31.1 garantiert, daß jede hinzugefügte Kante ein Teil des minimalen Spannbaumes ist.

Abbildung 31.3 veranschaulicht die ersten vier Schritte, wenn diese Strategie auf den Graph aus unserem Beispiel angewandt wird, beginnend bei Knoten A. Der zu A »nächstgelegene« Knoten (der mittels einer Kante minimalen Gewichts mit A verbunden ist) ist B, demnach ist AB im minimalen Spannbaum enthalten. Von allen Kanten, die A oder B berühren, hat die Kante BC das kleinste Gewicht, so daß sie zum Baum hinzugefügt wird, und Knoten C wird als nächster besucht. Danach ist der nächste Knoten für A, B oder C nunmehr D, so daß BD zum Baum hinzugefügt wird. Die Vollendung des Prozesses wird weiter unten in der Abbildung 31.5 dargestellt, nachdem wir die Implementation erörtert haben.

Abbildung 31.3
Abbildung 31.3 Anfangsschritte der Erzeugung eines minimalen Spannbäumes.

Wie implementieren wir diese Strategie nun? Inzwischen hat der Leser sicher die grundlegende Struktur von Baumknoten, Randknoten und noch nicht besuchten Knoten erkannt, die für die Strategien der Tiefen- und Breitensuche aus Kapitel 29 charakteristisch waren. Es zeigt sich, daß das gleiche Verfahren anwendbar ist, unter Verwendung einer Prioritätswarteschlange (anstelle eines Stapels oder einer Warteschlange) zum Speichern der zum Rand gehörenden Knoten.


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