algorithm - Prims算法中最小生成树的π[v] ←u步是什么意思？

Question

在这个关于最小生成树的 Prims 算法的 MIT 视频中，教授π[v] ←u在 71:16 秒时解释了这一点。但我不明白为什么我们需要这一步。这个符号 π[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 算法找到的路径（= 生成树的边缘）。