Prims Algorithm for minimum spanning tree.

Procedure Prims (G, W, S)

The above procedure subalgorithm finds the minimum spanning tree of a given graph ‘g’. The procedure takes the advantage of priority queue data structure. It uses three arrays ‘color’, ‘pre’ and ‘key’.

Step 1 Initialization

for a ¬ V1, V2 .... Vn R a Î V

{

set key [a] ¬ + ¥

set color [a] ¬ white

} REnd of loop

Step 2 start at root vertex

set key [S] ¬ 0

set pre [S] ¬ NULL

set Q ¬ call to prio Queues (V)

put vertices in Q.

Step 3 Loop, searches until all vertices in MST

while (non-empty) (Q))

{

set a ¬ Extract_Minimum (Q) R vertex with light edge.

start loop 2

for V ¬ V1, V2 .... Adj [a] R V Î Adj [a]

{

if (color [V] = white) & & (W (a, V) <>

{

set key [V] ¬ W (a, V)

new lighter edge out of V

call to Decrease key ( Q, V, key [V])

set pre [V] ¬ a

End of loop 2

set color [a] ¬ black

End of loop 1

Step 4 return at the point of call

return.