Minimaler Spannbaum: Kruskal und Prim verstehen

Zuerst die Bausteine. Ein Graph besteht aus Knoten (Punkten) und Kanten (Verbindungen). Ungerichtet heißt: Die Kanten haben keine Richtung. Ein Pfad ist ein Weg, der keinen Knoten doppelt benutzt. Ein Kreis ist ein Weg, der wieder zum Startknoten zurückführt. Zusammenhängend heißt: Von jedem Knoten kommst du zu jedem anderen.

Ein Baum ist ein zusammenhängender, kreisfreier, ungerichteter Graph. Ein Baum mit n Knoten hat genau n − 1 Kanten. Zwischen je zwei Knoten gibt es genau einen Pfad. Entfernst du eine beliebige Kante, hängt der Baum nicht mehr zusammen. Fügst du zwischen zwei beliebigen Knoten eine weitere Kante hinzu, entsteht ein Kreis.

Ein Spannbaum eines Graphen ist ein Teilgraph, der ein Baum ist und alle Knoten des Graphen enthält. Andere Namen sind „aufspannender Baum“ und „Gerüst“. Spannbäume gibt es nur in zusammenhängenden Graphen. Einen Spannbaum, der nicht unbedingt minimal ist, findest du auch mit Breitensuche oder Tiefensuche.

In einem Graphen mit Kantengewichten (zum Beispiel Kabelkosten) ist das Gewicht des Graphen die Summe seiner Kantengewichte. Ein Spannbaum heißt minimal, wenn es im selben Graphen keinen anderen Spannbaum mit geringerem Gewicht gibt. Man schreibt oft MST, nach dem englischen Minimum Spanning Tree. Sind alle Kantengewichte verschieden, gibt es genau einen minimalen Spannbaum.

Kruskal arbeitet in zwei Phasen. Erst sortierst du alle Kanten aufsteigend nach ihrem Gewicht. Dann gehst du die sortierten Kanten der Reihe nach durch. Du wählst jeweils die kürzeste noch nicht gewählte Kante, die mit den schon gewählten Kanten keinen Kreis bildet. „Kürzeste Kante“ heißt: die Kante mit dem kleinsten Kantengewicht. Der Graph muss dafür zusammenhängend, kantengewichtet und endlich sein.

Sind mehrere Kanten gleich leicht, darfst du eine beliebige davon zuerst nehmen. Deshalb kann Kruskal bei gleichen Gewichten bei jedem Durchlauf andere Ergebnisse liefern. Alle diese Ergebnisse sind minimale Spannbäume.

Prim startet mit einem einzigen beliebigen Knoten als Baum T. In jedem Schritt suchst du die Kante mit minimalem Gewicht, die einen weiteren Knoten mit T verbindet. Diese Kante und der neue Knoten kommen zu T. Du wiederholst das, bis alle Knoten in T sind. Dann ist T ein minimaler Spannbaum. Der Startknoten ist frei wählbar.

Beide Verfahren sind zwei Wege zum minimalen Spannbaum. Im Beispiel unten kennst du nicht alle Gewichte, denn es kommt nur auf die Reihenfolge und die Kreisprüfung an.

Bei Kruskal entscheidet allein der Kreis. Eine Kante kommt in den Baum, wenn sie zwei Knoten verbindet, die noch nicht durch einen Pfad schon gewählter Kanten verbunden sind. Sind beide Knoten schon verbunden, würde die Kante einen Kreis schließen. Dann wird sie verworfen und danach nicht mehr betrachtet. Im Beispiel mit den Knoten A bis G gilt das für BD.

Auch gleich lange Kanten werden einzeln geprüft. Im Beispiel wird nach AB (Länge 7) auch BE (Länge 7) gewählt, weil BE keinen Kreis bildet. Die Kante EG ist die letzte, weil alle kürzeren oder gleich langen Kanten schon gewählt sind oder einen Kreis bilden würden.

Bei Prim musst du keinen Kreis prüfen. Prim betrachtet nur Kanten, die einen Knoten außerhalb des Baums mit dem Baum verbinden. Deshalb entsteht nie ein Kreis. Führen zwei Kanten zum selben neuen Knoten, nimmst du nur die leichtere. Wichtig: Es muss immer die aktuell leichteste Kante gewählt werden, sonst ist das Ergebnis nicht korrekt.

Ein kürzester Pfad liegt zwischen zwei bestimmten, verschiedenen Knoten. Unter allen Pfaden dazwischen hat er die kleinste Länge bezüglich der Kantengewichte. Haben alle Kanten das Gewicht 1, ist es der Pfad mit den wenigsten Kanten. Der Algorithmus von Dijkstra berechnet kürzeste Pfade von einem Startknoten zu allen übrigen Knoten. Er wählt dafür unter den unbesuchten Knoten den mit der kleinsten Distanz.

Ein minimaler Spannbaum enthält dagegen alle Knoten und hat unter allen Spannbäumen das geringste Gesamtgewicht. Er berechnet sich mit Prim oder Kruskal. Der Baum aus den kürzesten Wegen von einem Startknoten ist zwar ein Spannbaum, aber nicht notwendigerweise minimal.

Ein kleines Beispiel mit vier Knoten: Die Kanten sind A-B (1), B-C (2), C-D (3) und A-D (4). Kruskal verwirft A-D, denn A und D sind dann schon verbunden. Dijkstra mit Start bei A findet aber für D genau die Kante A-D mit Länge 4 als kürzesten Weg. Für C ist der kürzeste Weg A → B → C mit Länge 3. Die Kante A-D gehört also zu einem kürzesten Weg, aber nicht zum minimalen Spannbaum.