Kruskal-Algorithmus

graph LR a((A)) b((B)) c((C)) d((D)) e((E)) a -- 3 --- b b -- 7 --- c a -- 1 --- c b -- 5 --- d b -- 1 --- e c -- 2 --- d d -- 7 --- e

Ein Beispielgraph

Der Kruskal-Algorithmus ist ein Algorithmus, der zu einem gegebenen gewichteten Graphen einen minimalen Spannbaum erzeugt.

Der Algorithmus wurde 1956 von Joseph Kruskal entworfen und wie folgt beschrieben:

Führe den folgenden Schritt so oft wie möglich aus: Wähle unter den noch nicht ausgewählten Kanten von $G$ (dem Graphen) die kürzeste Kante, die mit den schon gewählten Kanten keinen Kreis bildet.

Beispiel

So erzeugt der Kruskal-Algorithmus aus dem Beispielgraphen einen MST:

graph LR a((A)) b((B)) c((C)) d((D)) e((E)) a -- 3 --- b b -- 7 --- c a -- 1 --- c b -- 5 --- d b -- 1 --- e c -- 2 --- d d -- 7 --- e linkStyle default stroke:lightgray, fill:none; linkStyle 2 stroke:#00b169, color:green;

Schritt 1

graph LR a((A)) b((B)) c((C)) d((D)) e((E)) a -- 3 --- b b -- 7 --- c a -- 1 --- c b -- 5 --- d b -- 1 --- e c -- 2 --- d d -- 7 --- e linkStyle default stroke:lightgray, fill:none; linkStyle 2 stroke:#00b169, color:green; linkStyle 4 stroke:#00b169, color:green;

Schritt 2

graph LR a((A)) b((B)) c((C)) d((D)) e((E)) a -- 3 --- b b -- 7 --- c a -- 1 --- c b -- 5 --- d b -- 1 --- e c -- 2 --- d d -- 7 --- e linkStyle default stroke:lightgray, fill:none; linkStyle 2 stroke:#00b169, color:green; linkStyle 4 stroke:#00b169, color:green; linkStyle 5 stroke:#00b169, color:green;

Schritt 3

graph LR a((A)) b((B)) c((C)) d((D)) e((E)) a -- 3 --- b b -- 7 --- c a -- 1 --- c b -- 5 --- d b -- 1 --- e c -- 2 --- d d -- 7 --- e linkStyle default stroke:lightgray, fill:none; linkStyle 2 stroke:#00b169, color:green; linkStyle 4 stroke:#00b169, color:green; linkStyle 5 stroke:#00b169, color:green; linkStyle 0 stroke:#00b169, color:green;

Schritt 4

Je nach Implementierung könnte im ersten Schritt auch die Kante B—E ausgewählt werden.

Nach dem vierten Schritt gibt es keine Kante mehr im Graphen, die keinen Kreis erzeugt, darum terminiert der Algorithmus.

Weblinks

• Der Kruskal-Algorithmus visualisiert auf VisuAlgo.net 🇬🇧

Quellen

Algorithmen auf Graphen

Suche: Breitensuche | Tiefensuche

Kürzeste Wege: Dijkstra-Algorithmus | Bellman-Ford-Algorithmus

Minimale Spannbäume: Kruskal-Algorithmus | Prim-Algorithmus | Borůvka-Algorithmus