PRIM’S ALGORITHM

 

PRIM’S ALGORITHM

 

Prim’s algorithm is a greedy algorithm that is used to find a minimum spanning tree (MST) of a given connected weighted graph. This algorithm is preferred when the graph is dense. The dense graph is a graph in which there is a large number of edges in the graph. This algorithm can be applied to only undirected connected graph and there should not be any negative weighted edge. In this case, the algorithm is quite efficient. Since there are no non-negative weight cycles, there will be a shortest path whenever there is a path.

 

 

 

 

 

 

The steps to find minimum spanning tree using Prim’s algorithm are as follows:

1. If graph has loops and parallel edges than remove loops and parallel edges of that graph.

2. Randomly choose any node, labelling it with a distance of 0 and all other nodes as ∞. The chosen node is treated as current node and considered as visited. All other nodes are considered as unvisited.

3. Identify all the unvisited nodes that are presently connected to the current node. Calculate the distance from the unvisited nodes to the current node.

4. Label each of the vertices with their corresponding weight to the current node, but relabel of a node, if it is less than the previous value of the label. Each time, the nodes are labelled with its weights; keep track of the path with the smallest weight.

5. Mark the current node as visited by coloring over it. Once a vertex is visited, we not need to look at it again.

6. From all the unvisited nodes, find out the node which has minimum weight to the current node, consider this node as visited and treat it as the current working node.

7. Repeat steps 3, 4 and 5 until all nodes are visited

8. After completed all steps get desired MST.

 

Algorithm:

/* S= set of visited node, Q= Queue, G=Graph, w=Weight */

Prims MST (G, w, S)

{

Initialization (G, S)

S ←Ø             // the set of visited nodes is initially empty

Q← v [G ]      // The queue is initially containing all node

while (Q = Ø )         // Queue not empty

do u← extract min (Q )         // select the minimum distance of Q

S ←SU{u}            // the u is added in visited set S

For each vertex v ϵ adj(u)

do relax (u, v, w)

}

Initialization (G, S)

{

For each vertex v ϵ adj (u)

d [v] ←∞            //Unknown Distance from source node

π[v] ←nil           // Predecessor node initially nil.

d[s] ←0            //Distance of source nodes is zero

}

Relax (u, v, w)

{

If d[v]>w [u, v]        // comparing new distance with existing value

{

d[v] ← w [u, v]

π[u] ←u

  }

}

 

 

 

 

 

 

 

Using Prim’s algorithm, calculation the minimum spanning tree is given in the following graph.

 

Step1: Redraw the graph as following:

 

 

 

Consider the source node as A. Therefore, A will be the current working node and can be treated as visited.

 

 

 

 

 

 

 

 

 

Nodes	A	B	C	D	E	F
Distance d(v)	0	ꝏ	ꝏ	ꝏ	ꝏ	ꝏ
Distance from ℼ[v]	A
Status	Visited	Unvisited	Unvisited	Unvisited	Unvisited	Unvisited

 

 

Step2:

We can calculate the weights of unvisited adjacent nodes of current node A. The unvisited nodes of A are B, C, and D.

Now,           Distance [B]> distance (A, B) ⇨ ∞ > 10

So, relabel is required in node B.

Distance [C]> distance (A, C) ⇨ ∞ > 6

So, relabel is required in node C.

Distance [D]> distance (A, D) ⇨∞ > 3

So, relabel is required in node D.

 

 

 

 

 

Nodes	A	B	C	D	E	F
Distance d(v)	0	10	6	3	ꝏ	ꝏ
Distance from ℼ[v]	A	A	A	A
Status	Visited	Unvisited	Unvisited	Unvisited	Unvisited	Unvisited

 

We can discover the smallest distance from A to the unvisited node which is D, traversing through A to D and now D can be considered as the current node.

 

Step3:

We can calculate the weights of unvisited adjacent nodes of current node D. The unvisited nodes of D are C and F.

Now,

Distance[C] > Distance (D, C) ⇨ 6 > 5

So, relabel is required in node C.

Distance [F] > Distance (D, F) ⇨ ∞ > 4

So, relabel is required in node F.

 

Nodes	A	B	C	D	E	F
Distance d(v)	0	10	5	3	ꝏ	4
Distance from ℼ[v]	A	A	D	A		D
Status	Visited	Unvisited	Unvisited	Visited	Unvisited	Unvisited

 

We can discover the smallest distance from D to the unvisited node which is F, traversing through D to F and now F can be considered as the current node.

Step 4:

Unvisited adjacent of current working node of F is E

Now,

Distance [E]> Distance (F, E) ⇨ ∞ > 3

So, relabel is required in node E.

 

 

Nodes	A	B	C	D	E	F
Distance d(v)	0	10	5	3	3	4
Distance from ℼ[v]	A	A	D	A	F	D
Status	Visited	Unvisited	Unvisited	Visited	Unvisited	Visited

 

We can discover the smallest distance from F to the unvisited node which is E, traversing from F to E and now E can be considered as the current node.

Step 5:

Unvisited current node of E is C and B.

Now,

Distance [B]> Distance (E, B) ⇨ 10 > 7

So, relabel is required in node.

Distance [C]> Distance (E, C) ⇨ 5< 6

So, relabel is not required.

 

 

 

Nodes	A	B	C	D	E	F
Distance d(v)	0	7	5	3	3	4
Distance from ℼ[v]	A	E	D	A	F	D
Status	Visited	Unvisited	Unvisited	Visited	Visited	Visited

 

We can discover the smallest distance from D to the unvisited node which is C, traversing from D to C and now C can be considered as the current node.

 

Step6:

From current node C the unvisited node is B.

Distance [B] > Distance (C, B).

So, relabel is required.

 

 

 

 

 

 

Nodes	A	B	C	D	E	F
Distance d(v)	0	2	5	3	3	4
Distance from ℼ[v]	A	C	A	A	F	D
Status	Visited	Unvisited	Visited	Visited	Visited	Visited

 

Now, only unvisited node is B. So, Traverse from C to B and mark B as visited.

Nodes	A	B	C	D	E	F
Distance d(v)	0	2	5	3	3	4
Distance from ℼ[v]	A	C	A	A	F	D
Status	Visited	Visited	Visited	Visited	Visited	Visited

 

 

Therefore, the minimum spanning tree of the given graph is given below:

 

 

The weight of minimum spanning tree will be:

= (A, D) + (D, F) + (F, E) + (D, C) + (C, B)

= 3+4+3+5+2

= 17

 

COMPLEXITY

 

Finding the minimum distance is O (V) and overall complexity with adjacency list representation is O (V2). If queue is kept as a binary heap, relax will need a decrease-key operation which is O (logV) and the overall complexity is O (V log V + E log V) i.e., O (E log V). If queue is kept as a Fibonacci heap, decrease-key has an amortized complexity O (1) and the overall complexity is O (E+V log V).