TU Wien:Algorithmen und Datenstrukturen 1 VU (Raidl)/Übungen SS09/Beispiel 34

Führen Sie anhand des nachstehend abgebildeten Graphen den Algorithmus von Kruskal für das Finden eines minimalen Spannbaums durch.

Geben Sie jeden Schritt des Algorithmus an:

(a) Geben Sie den Zustand aller benötigten Datenstrukturen (Knotenmenge, Kantenmenge und Gewicht des aktuellen Spannbaums) nach jeder Iteration des Algorithmus an. Schreiben Sie insbesondere in jeder Iteration deutlich den neu hinzugekommenen Knoten und die entsprechende Kante dazu.

(b) Markieren Sie am Ende Ihrer Berechnungen jene Kanten des Graphen in der Abbildung, die den minimalen Spannbaum bilden, und geben Sie das Gewicht des minimalen Spannbaums an.

Lösung

Teil A

$(A,C),(C,G),(A,D),(C,E),(B,C)$