2
$\begingroup$

There is an obvious similarity in workings between Prim's algorithm and Dijkstra's algorithm, however I see no reason for Prim's algorithm to keep track of a node's parent. In Dijkstra's algorithm, the parent of the node needs to be tracked in order to follow the chain back to the original node to determine the distance from the source, however since Prim's algorithm only requires knowledge of the distance from the minimal spanning tree, rather than a specific node, there would be no reason to track the parent.

Please refer to the following pseudocode as reference:

PRIM(V, E, w, r )
  Q ← { }
  for each u in V do
    key[u] ← ∞
    π[u] ← NIL
    INSERT(Q, u)
  DECREASE-KEY(Q, r, 0)    ▷ key[r ] ← 0
  while Q is not empty do 
    u ← EXTRACT-MIN(Q)
    for each v in Adj[u] do 
      if v in Q and w(u, v) < key[v] then 
        π[v] ← u
        DECREASE-KEY(Q, v, w(u, v))
$\endgroup$
0
4
$\begingroup$

Keeping the parent of each vertex is not a requirement to get the minimum spanning tree. For example, the algorithm as described on Wikipedia does not do this.

However, it's worth noting that there is more than one representation of an MST. In certain applications, it might be useful to quickly find the parent of a particular vertex.

$\endgroup$
1
  • 3
    $\begingroup$ Could you provide a possible application where tracking the parent is relevant? $\endgroup$
    – user1422
    Aug 6 '12 at 4:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy