Direkt zum Inhalt

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 k1K(G) minimaler Länge. Hat man die Kanten k1, k2, …, ki bereits gewählt, so bestimme man eine Kante \begin{eqnarray}{k}_{i+1}\in K(G)-\{{k}_{1},{k}_{2},\ldots,{k}_{i}\}\end{eqnarray}

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.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos