Explanation :
The Prim’s algorithm is a type of greedy algorithm which is used to find the MST of a weighted undirected graph.
Watch this video for full understanding.
Code :
#include<bits/stdc++.h> using namespace std; #define V 6 //No of vertices int selectMinVertex(vector<int>& value,vector<bool>& setMST) { int minimum = INT_MAX; int vertex; for(int i=0;i<V;++i) { if(setMST[i]==false && value[i]<minimum) { vertex = i; minimum = value[i]; } } return vertex; } void findMST(int graph[V][V]) { int parent[V]; //Stores MST vector<int> value(V,INT_MAX); //Used for edge relaxation vector<bool> setMST(V,false); //TRUE->Vertex is included in MST //Assuming start point as Node-0 parent[0] = -1; //Start node has no parent value[0] = 0; //start node has value=0 to get picked 1st //Form MST with (V-1) edges for(int i=0;i<V-1;++i) { //Select best Vertex by applying greedy method int U = selectMinVertex(value,setMST); setMST[U] = true; //Include new Vertex in MST //Relax adjacent vertices (not yet included in MST) for(int j=0;j<V;++j) { /* 3 constraints to relax:- 1.Edge is present from U to j. 2.Vertex j is not included in MST 3.Edge weight is smaller than current edge weight */ if(graph[U][j]!=0 && setMST[j]==false && graph[U][j]<value[j]) { value[j] = graph[U][j]; parent[j] = U; } } } //Print MST for(int i=1;i<V;++i) cout<<"U->V: "<<parent[i]<<"->"<<i<<" wt = "<<graph[parent[i]][i]<<"\n"; } int main() { int graph[V][V] = { {0, 4, 6, 0, 0, 0}, {4, 0, 6, 3, 4, 0}, {6, 6, 0, 1, 8, 0}, {0, 3, 1, 0, 2, 3}, {0, 4, 8, 2, 0, 7}, {0, 0, 0, 3, 7, 0} }; findMST(graph); return 0; } //TIME COMPLEXITY: O(V^2)