write prims algorithm nb s prims algorithm

Question

Write Prim's Algorithm.  

Ans: Prim's algorithm to find out a minimum spanning tree from a weighted graph in step by step form is given below. 

Let G = (V, E) be graph and S = (V_S, E_S) be the spanning tree to be found from G.

Step 1: Choose a vertex v1 of V and initialize 

VS = {v1} and

ES

= {}

Step 2: Choose a nearest neighbor of v_i from V that is adjacent to some v_j∈V_S and that edge (v_i, v_j) does not form a cycle with members edge of E_S. Set

V_S = V_S ∪{v_i} and

E_S = E_S ∪{(v_i, v_j)}  

Step 3: Again Repeat step2 until |E_s| = |V| - 1.