在最小生成树的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的算法找到的路径（=生成树的边缘）。