Search code examples
algorithmdata-structuresgraph-algorithmminimum-spanning-tree

What does π[v] ←u step mean in Prims algorithm for minimum spanning tree?


In this MIT video regarding Prims algorithm for minimum spanniing tree the professor explains π[v] ←u at time 71:16 seconds . But I do not understand why we need this step . What does this notation π[v] ←u mean actually ? Also what does the last line in the algorithm that follows mean ? The entire algorithm given in the source is as follows :

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

Solution

  • π is just any old array variable. So this line of code isn’t really different from the other assignments.

    What it does in the algorithm however is save the predecessor node of the current node. π is sometimes also called the predecessor function because for any given node n, π[n] gives you the predecessor of that node (after the algorithm has completed).

    So π can be used to reconstruct the path (= the edges of the spanning tree) found by Prim’s algorithm.