Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Foliensatz 14, Seiten 89 bis 93 Algorithmus von Prim
Hallo,
das Beispiel zum Algorithmus von Prim gibt mir Rätsel auf.
Mir ist schon klar, dass immer die billigste Kante / der billigste Knoten dazu genommen wird. Ich habe aber noch nicht verstanden, was man damit
zum Schluss dann eigentlich erreicht??
Am Ende hat man dann eh den ganzen Graphen eingesackt. Toll. Was ist daran jetzt minimal ?
Hier gehts zu den Folien
https://www2.cs.fau.de/teaching/WS2013/AuD/slides/secure/aud-14.pdf
NACHTRAG: Ich sehe jetzt erst, dass manche Verbindungslinien dicker sind als andere. Diese gehören dann wohl zum Spannbaum. AHHH, ich glaube jetzt komme ich langsam dahinter…
Ich denke du hast es 
Wichtig ist eine Folie vorher der Halbsatz “Solange T noch nicht alle Knoten enthält”.
Man hört auf, sobald der Spannbaum alle Knoten erreicht und fügt auch keine Kanten hinzu, die keine neuen Knoten zum Spannbaum hinzufügen.