Algorithmus von Kruskal zur Bestimmung eines MST

Der Algorithmus verfolgt die Idee, immer die kürzeste Kante des Graphen dem Baum hinzuzufügen, wenn dadurch nicht ein Zyklus entsteht und die Kante damit überflüssig ist. Es entstehen dabei zunächst viele einzelne Bäume (ein Wald), die sukzessive zu einem einzigen Baum zusammengeführt werden. Um die Zyklen leicht erkennen zu können, werden die Knoten jedes einzelnen Baums in einer eigenen Farbe eingefärbt. Zunächst werden die Kanten also nach ihrem Gewicht sortiert und dann für jede Kante folgende Regeln beachtet:

• haben beide Knoten noch keine Farbe (Farbe 0), dann gehören sie bisher zu keinem Baum und werden beide in einer noch nicht benutzen Farbe gefärbt.
• hat ein Knoten eine Farbe und der andere noch nicht, wird der Baum des farbigen Knotens erweitert. Die Farbe wird für den noch nicht gefärbten Knoten übernommen.
• haben beide Knoten eine unterschiedliche Farbe, dann werden zwei Bäume zu einem vereinigt. Alle Knoten des zweiten Baums werden mit der Farbe des ersten eingefärbt.
• haben beide Knoten die gleiche Farbe, gehören sie zum gleichen Baum. Die Kante darf nicht eingefügt werden, da ein Zyklus entstehen würde.

Außer in Fall 4 wird außerdem die Kante markiert, da sie zum minimalen Spannbaum gehört.