liefert in einem zusammenhängenden und bewerteten GraphenG 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 k₁ ∈ K(G) minimaler Länge. Hat man die Kanten k₁, k₂, …, k_i 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 TeilgraphG[{k₁, k₂, …, k_i+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.