pseudocode für implementierung von primMST mit heap

[robzero6]

hat sich schon jemand gedanken dazu gemacht?
komme irgendwie mit hilfe der äusserst minimalen angaben im skriptum
auf keinen grünen zweig.....

speichert man nun die kanten im heap oder die noch verbleibenden knoten mit ihren listen?


ciao, Roberto

[Georg Kraml]

speichert man nun die kanten im heap oder die noch verbleibenden knoten mit ihren listen?

Nur die Kanten. Die lassen sich in der Regel ja einfach als Paare von Knoten(zeigern) repräsentieren und ermöglich damit den Zugriff auf die "Listen" (du meinst Adjazenzlisten?) über die "ursprüngliche" Datenstruktur.

.

[Merlin]

Ja, vielleicht wär eine Testfrage ja:

Geben Sie einen Greedy-Algorithmus zum auffinden eines minmalen Spannbaums mittels Implementation eines Heaps an.

Dann würde ich bei Schritt 5 einfügen:
Kante = HeapSort();

wichtig ist dann nicht zu vergessen, bei jedem Hinzufügen einer Kante muss ich den Heap aktualisieren.

Ich würd ihn gleich immer neu aufbauen, also ErstelleHeap(M)
wobei M die Menge aller Kanten e (u,v) mit u e C und v e V\C.Wahrscheinlicht ists aber besser das irgendwie mit dem Versickern zu machen...
(Beim Heap-bsp bin bei der letzen Prüfung durchgefallen http://hades.gothic.at/iforum/images/smilies/disturbed.gif)