Lexikon der Mathematik: Kruskal, Algorithmus von
liefert in einem zusammenhängenden und bewerteten Graphen G mit der Komplexität O(|K(G)| log |K(G)|) einen minimal spannenden Baum von G.
Bei diesem Algorithmus aus dem Jahre 1956 von J.B. Kruskal läßt man im Graphen G einen Wald wie folgt wachsen. Man beginne mit einer Kante k1 ∈ K(G) minimaler Länge. Hat man die Kanten k1, k2, …, ki bereits gewählt, so bestimme man eine Kante
minimaler Länge so, daß der induzierte Teilgraph G[{k1, k2, …, ki+1}] keinen Kreis besitzt, also ein Wald ist. Hat man nach dieser Vorschrift |E(G)| − 1 Kanten gewählt, so erhält man schließlich einen minimal spannenden Baum von G.
Zum praktischen Gebrauch dieses Algorithmus’ ist es günstig, die |K(G)| bewerteten Kanten zunächst der Größe nach zu ordnen. Spezielle Sortieralgorithmen ermöglichen dies mit einem Auf-wand von O(|K(G)| log |K(G)|). Der Algorithmus von Kruskal liefert entsprechend modifiziert auch Maximalgerüste.
Schreiben Sie uns!