The Kruskal Algorithm

Der Kruskal-Algorithmus ist ein Algorithmus aus der Graphentheorie, der dazu dient, den minimalen Spannbaum (MST) eines ungerichteten, gewichteten Graphen zu finden. Ein Spannbaum eines Graphen ist ein Teilgraph, der alle Knoten des Graphen enthält und keine Zyklen aufweist. Ein gewichteter Graph ist ein Graph, bei dem jeder Kante ein Gewicht (eine Kostenfunktion) zugeordnet ist.

Der Kruskal-Algorithmus arbeitet nach dem Greedy-Prinzip, d.h. er trifft bei jeder Schleife die jeweils beste Entscheidung und hofft darauf, dass diese Entscheidung in der Gesamtbetrachtung den bestmöglichen Spannbaum liefert. Der Algorithmus läuft wie folgt ab:

1. Sortiere alle Kanten des Graphen nach Gewicht.
2. Erstelle einen leeren Teilgraphen als MST.
3. Gehe alle Kanten in der sortierten Reihenfolge durch.
4. Füge die Kante zum MST hinzu, wenn sie keinen Zyklus erzeugt.

Die Idee hinter dem Algorithmus ist, dass man immer die günstigste Kante nimmt, die noch nicht zu einem Zyklus im MST führt. Wenn man so vorgeht, wird man immer den günstigsten Spannbaum erhalten.

Damit der Algorithmus keine Zyklen erzeugt, sind die Knoten in zusammenhängende Komponenten eingeteilt, und zwar basierend auf den bereits zum Spannbaum hinzugefügten Kanten. Am Anfang befinden sich alle Knoten in verschieden Komponenten. Sobald eine Kante hinzugefügt wird, werden die beiden verbundenen Komponenten zu einer einzigen Komponente. Fügt man nun ausschließlich Kanten hinzu, die zwei Komponenten verbinden, kann dabei kein Zyklus erzeugt werden.

In folgender Animation siehst du die zusammenhängenden Komponenten jeweils in unterschiedlichen Farben.