Algorithmus von Kruskal

Dieser Artikel von Wikipedia ist u.U. veraltet. Die neue Version gibt es hier.

Inhaltsverzeichnis

1 Einleitung

2 Grundidee

3 Implementation des Kruskal-Algorithmus

4 Algorithmus von Prim

Einleitung

Der Algorithmus von Kruskal (1956) ist ein Algorithmus zur Berechnung minimal spannenden Bäumen in zusammenhängenden ungerichteten kantengewichteten Graphen .

Die Grundidee ist die Kanten in Reihenfolge aufsteigender Kantengewichte zu durchlaufen und jede zu wählen die mit allen zuvor gewählten keinen Kreis schließt. Die Laufzeit des Algorithmus beruht wesentlichen auf dem notwendigen Sortieren der Kanten beträgt <math>O(n + m \log n) </math> m die Zahl der Kanten und n die Zahl der Knoten ist.

In unzusammenhängenden Graphen findet der Algorithmus einen Wald von spannenden Bäumen für jede der Zusammenhangskomponenten .

Implementation des Kruskal-Algorithmus

Zur Bestimmung der leichtesten Kante wird Menge E in der Regel sortiert. Zur Implementation bestmöglicher Laufzeit muss in konstanter Zeit ermittelt ob eine Kante zwei Komponenten verbindet und zum minimalen Spannbaum gehört oder ob sie Kreis schließen würde und daher verworfen werden

Dazu wird zu jedem Knoten ein auf seine Komponente gespeichert. Die Vereinigung von ist amortisiert in O(log n) möglich. Dazu wird jeder Komponente ihre Größe gespeichert so dass einer Vereinigung immer die kleinere Komponente der hinzugefügt werden kann. Insgesamt kann somit jeder höchstens (log n)-mal in eine anderen Komponente werden.

Algorithmus von Prim

Mit Hilfe von Fibonacci-Heaps und des Algorithmus von Prim lässt sich ein minimal spannender Baum etwas effizienter in Laufzeit <math>O(m + n\log bestimmen.

Bücher zum Thema Algorithmus von Kruskal

Dieser Artikel von Wikipedia unterliegt der GNU FDL.

Impressum • Lesezeichen setzen • Seite versenden • Seite drucken

HTML-Code zum Verweis auf diese Seite:
<a href="http://www.uni-protokolle.de/Lexikon/Kruskal.html">Algorithmus von Kruskal </a>