//Author: Bishal Sarang //Prims Algorithm for MST /* Sample input 5 7 0 1 4 0 2 4 0 3 6 0 4 6 1 2 2 2 3 8 3 4 9 */ #include #define MAX 100 #define INF 1000000 using namespace std; //Adjacency List //Array of Vector Pairdist[v.second] vector< pair> adj[MAX]; //Store Distance of Vertex long long dist[MAX]; bool Visited[MAX]; int weight[MAX]; //Prims Algorithm Procedure void prims(int s, int v) { //Initialize all distances to infinite memset(dist, INF, sizeof(dist)); //Initialize all weight to 0 memset(weight, 0, sizeof(weight)); //Declare priority queue to extract minimum distance every time //Greedy approach priority_queue< pair , vector>, greater>> pq; //Initialize priority que with infinite distance and all the vertices for(int i = 0; i < v; i++) { pq.push({INF, i}); } dist[s] = 0; pq.push({0, s}); while(!pq.empty()) { //Extract minimum weight and pop it int w = pq.top().first; int u = pq.top().second; pq.pop(); //Put popped Value to visited set Visited[u] = true; for(auto v: adj[u]) { if(!Visited[v.second]) //If the vertex is already in MST Set Ignore { if( dist[v.second] > v.first ) { dist[v.second] = v.first; weight[v.second] = dist[v.second] ; pq.push({dist[v.second], v.second}); } } } } } int main() { //freopen("prims.txt", "r", stdin); int vertex, edges; cin >> vertex >> edges; int u, v, w; for(int i = 0; i < edges; i++) { //Input starting vertex, ending vertexand weight of edge cin >> u >> v >> w; //Add to the adjacency list adj[u].push_back({w, v}); adj[v].push_back({w, u}); } //Arbitarily Choose any vertex as source //I chose last input vertex //Call prim's procedure with arbitrary vertex u and number9f vertex prims(u, vertex); int sum =0; for(int i = 0; i < vertex; i++) sum += weight[i]; cout <<"MST Weight is: " << sum; return 0; }

Prim's Minimum Spanning Tree(MST)