Algorithmus von Kruskal

Algorithmus:
Der Algorithmus von Kruskal berechnet zu einem gewichteten Graphen $G=(V,E)$ einen minimalen Spannbaum, indem zunächst die Kantenliste vorsortiert wird und dann in den anfangs nur aus Knoten bestehenden Graph aufsteigend alle Kanten eingefügt werden, die keinen Kreis erzeugen.

Pseudocode mit Union-Find-Datenstruktur: (Kanten $e_i \in E$ seien vorsortiert)
$T = \{\}$
forall $v \in V$ do MakeNewSet($v$)
for $i$ = 1 to $m$
bestimme Knoten $u$ und $v$ zur Kante $e_i$
if Find($u$) $\neq$ Find($v$) then
$T = T \cup e_i$
Union(Find($u$),Find($v$))
endif enddo

Komplexität:
Der Algorithmus von Kruskal benötigt zum Vorsortieren Zeit $O(m \log m)$, mit einer Union-Find-Datenstruktur zusätzlich nur Zeit $O(m \log^* n)$.
Vorsicht: Für $m=O(n^2)$ (vollständiger Graph) wird der Algorithmus sehr langsam.