I boka sin implementasjon av MST-Prim legges ingen elementer til i mengden $A$, så jeg skjønner ikke hvordan spenntreet blir returnert. Er det siden MST-Prim hele tiden vedlikeholder ett enkelt tre? Hvorfor kan man ikke bare ha et enkele if-utsagn der $A = A \cup \{(u,u.p)\}$ hvis $\textit{parent}\neq\,$nil etter Dequeue fra $Q$?

Basert på Piazza-spørsmål fra 2018

Det er ingen grunn til det. Prims algoritme er nesten en traverseringsalgoritme (og hvis man ikke bruker $Q=G.V$, men bygger køen etterhvert som man finner noder, så er det en traverseringsalgoritme), og spenntreet blir bare traverseringstreet, angitt av $\pi$-attributten til hver node, akkurat som f.eks. BFS eller Dijkstra :-)

Det er mulig det var dette du stusset på, på side 634?

The algorithm implicitly maintains the set $A$ from Generic-MST as

$A = \{(v,v.\pi) : v \in V - \{r\} - Q\}\,.$

When the algorithm terminates, the min-priority queue $Q$ is empty; the minimum spanning tree $A$ for $G$ is thus

$A = \{(v,v.\pi) : v\in V - \{r\}\}\,.$

Nøkkelordet her er «implicitly». Den driver ikke og faktisk vedlikeholder en eksplisitt representasjon av $A$; kantmengden er bare implisitt definert av $\pi$-attributten.

Et annet spørsmål relatert til samme algoritme (MST-Prim): Det står i boka: «… all vertices that are not in the tree reside in a min-priority queue $Q$ based on a $\textit{key}$ attribute. For each vertex $v$, the attribute $v.\textit{key}$ is the minimum weight of any edge connecting $v$ to a vertex in the tree …».

Så, for å relatere dette til linje 7 i koden, $u =\,$Extract-Min$(Q)$. Hva betyr dette egentlig? Er det sånn at noden $u$ korresponderer til den letteste vekten som binder sammen en node (som ikke ligger i treet) og en node i treet ($A$)?

Ja :-) Og denne kanten er $(u.\pi,u)$. Decrease-Key kalles implisitt av Relax.

F.eks i figur 23.5 b): Tolker jeg det riktig om $u$ kan være node $a$ eller $b$. Og når dette valget er gjort, sjekker man videre alle naboene ($v$) til valget av $u$ og trekker en kant mellom, der den letteste vekten er funnet? Eller er jeg helt på bærtur?

Jeg er litt forvirra rundt hva som er $u$ og $v$ underveis i figur 23.5 siden $u$ bruker funksjonen Extract-Min$(Q)$ og $Q$ er alle noder som ikke ligger i treet.

Noden $u$ er alltid den med minst $\textit{key}$-felt, og til å begynne med så har alle noder her unntatt $s$ (dvs., $a$) et uendeig $\textit{key}$-felt. Derfor er det $a$ som plukkes ut først, og $b$ og $h$ får oppdatert sine key-felt til hv. 4 og 8. I neste runde er det derfor $b$ som har lavest $\textit{key}$ (valget står mellom 4, 8 og uendelig), og $c$ får nå et $\textit{key}$-felt på 8; $h$ endrer ikke sitt $\textit{key}$-felt, fordi 11 er større enn 8. Og så fortsetter det slik.

Du kan jo ta en kikk på simuleringen av Prim i forelesningsfoilene. Der ser du utviklingen trinn for trinn, sammen med gjennomgang av pseudokoden.