Algorithmus von Kruskal zur Bestimmung eines MST

(A1)

Untersuche im Graphentester den Algorithmus "MST (Kruskal)" zur Bestimmung des minimalen Spannbaums im Graphentester auf die Karte der größten Städte in Deutschland (02_deutschlandkarte.csv im Ordner 08_minimalspanningtree).

Versuche herauszufinden, wie der Algorithmus funktioniert, indem du ihn Schritt für Schritt ausführst.

Welche Situation muss vermieden werden? Fällt dir dafür eine einfache Lösung ein.

Beschreibe deinen so gefundenen Algorithmus in einem kurzen Text.

Verhgleiche deine Beschreibung mit den Musterlösung (unten) und bewerte, ob du das Vorgehen richtig nachvollzogen hast.

Beschreibung des Algorithmus von Kruskal

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.

(A2)