在最小生成樹的Prims算法中π[v]←u是什麼意思？

Question

在這MIT video regarding Prims algorithm for minimum spanniing tree教授在時間71:16秒解釋π[v] ←u。但我不明白爲什麼我們需要這一步。 π[v] ←u是什麼意思？算法中最後一行的含義是什麼？ 在源給出的整個算法如下：

Q←V 
key[v] ←∞for all v∈V 
key[s] ←0for some arbitrary s∈V 
while Q≠∅ 
do u←EXTRACT-MIN(Q) 
    foreach v∈Adj[u] 
    do ifv∈Qand w(u, v) < key[v] 
     then key[v] ←w(u, v)⊳DECREASE-KEY 
      π[v] ←u 

At the end, {(v, π[v])}forms the MST 

Answer 1

π是任何舊的數組變量。所以這行代碼與其他任務並沒有太大區別。

它是什麼確實但算法是保存前一個節點的當前節點。 π有時也被稱爲前任函數，因爲對於任何給定的節點n，π[n]給出了該節點的前身（算法完成後）。

所以π可以用來重建由Prim的算法找到的路徑（=生成樹的邊緣）。