Prim’s Minimum Spanning Tree

Algorithm
1) Create a set mstSet that keeps track of vertices already included in MST.
2) Assign a key value to all vertices in the input graph. Initialize all key values as INFINITE. Assign key value as 0 for the first vertex so that it is picked first.
3) While mstSet doesn’t include all vertices
   a) Pick a vertex u which is not there in mstSet and has minimum key value.
   b) Include u to mstSet.
   c) Update key value of all adjacent vertices of u. To update the key values, iterate through all adjacent vertices. For every adjacent vertex v, if weight of edge u-v is less than the previous key value of v, update the key value as weight of u-v

void primMST(int graph[V][V])
{
     int parent[V];
     int key[V];  
     bool mstSet[V]; 

     for (int i = 0; i < V; i++)
        key[i] = INT_MAX, mstSet[i] = false;
 
     key[0] = 0;   
     parent[0] = -1;
     for (int count = 0; count < V-1; count++)
     {
      
        int u = minKey(key, mstSet);
         mstSet[u] = true;
        for (int v = 0; v < V; v++){
        
        // graph[u][v] is non zero only for adjacent vertices of m
        // mstSet[v] is false for vertices not yet included in MST
        // Update the key only if graph[u][v] is smaller than key[v]
        if (graph[u][v] && mstSet[v] == false && graph[u][v] <  key[v])
             parent[v]  = u, key[v] = graph[u][v];
        }
         }
}