Probleme dieser Art entstehen immer dann, wenn ein kostengünstiges Netzwerk gesucht wird, welches z.B. eine Menge von Inseln durch Brücken oder ein Menge von Ortschaften durch Stromleitungen verbindet.
Ein Lösungsverfahren wurde von Kruskal vorgestellt:
Initialisiere einen Wald von Bäumen durch n isolierte Knoten;
Initialisiere einen Heap mit allen gewichteten Kanten;
while noch nicht genügend Kanten gefunden {
entferne die billigste Kante (x,y) aus dem Heap;
falls x und y im verschiedenen Baümen sind;
vereinige die beiden Bäume;
}
Die Korrektheit des Kruskal-Algorithmus folgt aus dem folgenden
Satz: Gegeben sei eine Partition der Knotenmenge . Sei die billigste Kante zwischen und . Dann gibt es einen MSB (Minimaler Spannbaum) der enthält. ( ist sogar in allen MSBs enthalten).
Beweis:
Annahme: sei nicht im MSB enthalten. Dann füge in den MSB ein. Es entsteht ein Zyklus, der über läuft. Entferne nun aus dem MSB. Es entsteht ein neuer, billigerer MSB. Dies ist ein Widerspruch zur Minimalität des Ausgangs-MSB.
Zur Verwaltung der Zusammenhangskomponenten notieren wir bei jedem Knoten in einer Arbeitsvariable chef denjenigen Knoten, der zur Zeit als Vorgesetzter für ihn fungiert. Ein Knoten, der sein eigener Vorgesetzter ist, übernimmt die Rolle des Repräsentanten für alle Knoten, die in seiner Zusammenhangskomponente liegen und die über die Variable chef direkt oder indirekt auf ihn verweisen. Bei der Vereinigung von zwei Zusammenhangskomponenten mit den Repräsentanten und muss nur einer der beiden (z.B. ) den anderen (d.h. ) als neuen Chef eintragen.
Damit die Suche nach dem aktuellen Chef nicht zu immer länger werdenden Verweisketten führt, benutzt man die Technik des Path halving: Längs des Weges von einem Knoten zu seinem Repräsentanten wird bei jedem Knoten der aktuelle Vater durch den Großvater ersetzt. Dieser Mehraufwand zahlt sich insofern aus, als bei der nächsten Repräsentantensuche der Weg nur noch halb so lang ist.
Hat der Graph Knoten und Kanten, dann beträgt der Aufwand für den Kruskal-Algorithmus lg*()), da maximal jede Kante einmal mit Aufwand aus dem Heap genommen wird. Der zusätzliche Faktor lg*() bezeichnet eine fast konstante, sehr langsam wachsende Funktion (nämlich die Inverse der Ackermannfunktion, für alle praktischen Werte von kleiner als 5). Sie wird verursacht durch das Testen mit Path Halving, ob zwei Knoten in derselben Zusammenhangskomponente liegen.
Source: Kruskal.java JavaDoc: Kruskal.html Source: KruskalTest.java JavaDoc: KruskalTest.html Applet:
Adjazenzlisten des Graphen: (D,B)10.0 (D,E)40.0 (D,F)30.0 (E,B)20.0 (E,C)20.0 (E,D)40.0 (E,F)70.0 (E,G)40.0 (F,A)20.0 (F,D)30.0 (F,E)70.0 (G,A)60.0 (G,C)50.0 (G,E)40.0 (A,B)80.0 (A,F)20.0 (A,G)60.0 (B,A)80.0 (B,C)10.0 (B,D)10.0 (B,E)20.0 (C,B)10.0 (C,E)20.0 (C,G)50.0 Der minimale Spannbaum besteht aus folgenden Kanten: (B,C) 10.0 (B,E) 20.0 (B,D) 10.0 (D,F) 30.0 (A,F) 20.0 (E,G) 40.0 |