CODEWITHSUNDEEP
pseudocodeprims-algorithm
shivam_b
shivam_b

Reputation: 19

unable to comprehend prims algorithm

Please help in understanding prims algo pseudocode(as it is in coreman and wiki) Prim's algorithm.

    MST-PRIM (G, w, r) {
for each u ∈ G.V
u.key = ∞
u.parent = NIL
r.key = 0
Q = G.V
while (Q ≠ ø)
//1
u = Extract-Min(Q)
for each v ∈ G.Adj[u]
if (v ∈ Q) and w(u,v) < v.key
v.parent = u
v.key = w(u,v)}

i am able to understand till 1 or while loop that r.key=0 ensure that neighours or adjacents of root are scanned first, but as u already belongs to Q(queue of nodes till now not included in prims minimum spanning tree) and v also in Q,will not help in generating prims MST.

also both coreman and thus wiki states

 1. A = { (v, v.parent) : v ∈ V - {r} - Q }.
2. The vertices already placed into the minimum spanning tree are those in V−Q.
3. For all vertices v ∈ Q, if v.parent ≠ NIL, then v.key < ∞ and v.key is the weight of a light edge

Prior to each iteration of the while loop of lines 6–11, (v, v.parent) connecting v ::to some vertex already placed into the minimum spanning tree.

as A is our MST then how 1. will help as v is already been included in our MST (as shown by v ∈ V - {r} - Q ) why then it should be included.

Upvotes: -1

Views: 1370

Answers (1)

DML
DML

Reputation: 544

For the part that you have doubts:

u = Extract-Min(Q) 
for each v ∈ G.Adj[u]
if (v ∈ Q) and w(u,v) < v.key
v.parent = u
v.key = w(u,v)

"For each vertex v, the attribute v:key is the minimum weight of any edge connecting to a vertex in the tree; by convention, key = ∞ if there is no such edge." (http://en.wikipedia.org/wiki/Prim's_algorithm)

Therefore, u = Extract-Min(Q) will get the vertex with the minimum key.

for each v ∈ G.Adj[u] will find all the neighbors of u.

if (v ∈ Q) and w(u,v) < v.key condition to eliminate cycle and check if path should be updated.

Then the following lines of code update the neighbors edges.

v.parent = u
v.key = w(u,v)

"Prior to each iteration of the while loop of lines 6–11, 1. A = { (v, v.parent) : v ∈ V - {r} - Q }. " (http://en.wikipedia.org/wiki/Prim's_algorithm)

Based on the above statement, before the while loop A is empty as Q = G.V! After the while loop you will get A contains all the vertices that form the MST. Each vertex v in A has a parent (v.parent). For root r, its parent is NIL. Root r is excluded due to the statement V - {r} but it exists in A thanks to its children in the form of v.parent.

Therefore in this link http://en.wikipedia.org/wiki/Prim's_algorithm , it states that: "2. The vertices already placed into the minimum spanning tree are those in V−Q."

and "When the algorithm terminates, the min-priority queue Q is empty; the minimum spanning tree A for G is thus A = { (v, v.parent) : v ∈ V - {r} }."

Upvotes: 1

Related Questions