TU Wien:Algorithmen und Datenstrukturen 1 VU (Raidl)/Übungen SS09/Beispiel 35
Lösen Sie die Aufgabe 34 erneut, diesmal aber unter Verwendung des Algorithmus von Prim. Wählen sie den Knoten C als Startknoten.
Kann sich im Allgemeinen das Ergebnis einer Durchführung des Algorithmus von Prim ändern, wenn man einen anderen Startknoten wählt? Begründen Sie Ihre Antwort!
Algorithmus von Prim[Bearbeiten | Quelltext bearbeiten]
Schriftliche Lösung[Bearbeiten | Quelltext bearbeiten]
In der Geschwungenen Klammer stehen die Knoten die in die Lösung aufgenommen wurden, nach dem Doppelpunkt das aktuelle Gesamtgewicht. Bei Nachbarn stehen alle adjazenten Knoten, in Klammer wie der günstigste Weg ist. Ausgewählte Knoten werden FETT markiert.
{C}: 0 -> Nachbarn: A(9), B(13), D(5), E(12), G(10)
{C,D}: 5 -> Nachbarn: A(9), B(13), E(12), G(7), H(1)
{C,D,H}: 6 -> Nachbarn: A(9), B(13), E(12), G(6)
{C,D,H,G}: 12 -> Nachbarn: A(9), B(13), E(12), F(8)
{C,D,H,G,F}: 20 -> Nachbarn: A(9), B(13), E(4)
{C,D,H,G,F,E}: 24 -> Nachbarn: A(9), B(2)
{C,D,H,G,F,E,B}: 26 -> Nachbarn: A(3)
{C,D,H,G,F,E,B,A}: 29
Graphische Lösung[Bearbeiten | Quelltext bearbeiten]
Änderung des Ergebnis[Bearbeiten | Quelltext bearbeiten]
Ja, im allgemeinen können die Ergebnisse sehr wohl abweichen, wenn zwei Kanten dasselbe Kantengewicht haben. Bei diesem Beispiel jedoch nicht, da das Kantengewicht der Kanten paarweise verschieden ist.