fork download
copy 
  1. //
  2. //  main.cpp
  3. //  Prim's Algorithm
  4. //
  5. //  Created by Himanshu on 28/05/23.
  6. //
  7.  
  8. #include <iostream>
  9. #include <vector>
  10. #include <queue>
  11. #include <limits>
  12.  
  13. using namespace std;
  14.  
  15. #define INF numeric_limits<int>::max()
  16. #define N 5
  17.  
  18. typedef pair<int, int> graphNode; // pair (node, weight)
  19. vector<vector<graphNode>> graph(N);
  20.  
  21. void printVector(vector<int> vec) {
  22.  
  23.     for (int i=0; i<N; i++) {
  24.         if (vec[i] == INF) {
  25.             cout<<"INF, ";
  26.         } else {
  27.             cout<<vec[i]<<", ";
  28.         }
  29.     }
  30.  
  31.     cout<<endl;
  32. }
  33.  
  34. void printMST(vector<int>& key, vector<int>& parent) {
  35.  
  36.     cout<<"Minimum Spanning Tree Edges:"<<endl<<endl;
  37.  
  38.     cout<<"Edge \tWeight"<<endl;
  39.  
  40.     for (int i = 1; i < N; ++i) {
  41.         if (parent[i] != -1) {
  42.             cout<<parent[i]<<" - "<<i<<"\t"<<key[i]<<endl;
  43.         }
  44.     }
  45. }
  46.  
  47. void primMST(int source, vector<int> &key, vector<int> &parent, vector<bool> &inMST) {
  48.  
  49.     int i = 1;
  50.  
  51.     // Custom comparator for the priority queue
  52.     auto cmp = [](const graphNode& a, const graphNode& b) {
  53.         return a.second > b.second;
  54.     };
  55.  
  56.     priority_queue<graphNode, vector<graphNode>, decltype(cmp)> pq(cmp);
  57.  
  58.     key[source] = 0; // Start with the source node
  59.     pq.push({source, key[source]});
  60.  
  61.     while (!pq.empty()) {
  62.         int u = pq.top().first;
  63.         pq.pop();
  64.  
  65.         inMST[u] = true;
  66.  
  67.         for (auto edge : graph[u]) {
  68.             int v = edge.first;
  69.             int weight = edge.second;
  70.  
  71.             if (!inMST[v] && weight < key[v]) {
  72.                 parent[v] = u;
  73.                 key[v] = weight;
  74.                 pq.push({v, key[v]});
  75.  
  76.                 cout<<"Iteration "<<i++<<":"<<endl;
  77.  
  78.                 cout<<"weight: "<<weight<<endl;
  79.                 cout<<"edge: "<<u<<" - "<<v<<endl;
  80.  
  81.                 cout<<"Key values: ";
  82.                 printVector(key);
  83.  
  84.                 cout<<"Parent values: ";
  85.                 printVector(parent);
  86.                 cout<<endl;
  87.  
  88.  
  89.             }
  90.         }
  91.     }
  92.  
  93. }
  94.  
  95. void initializeGraph() {
  96.  
  97.     // Example graph
  98.     // pair {node, weight}
  99.     graph[0].push_back({1, 4});
  100.     graph[0].push_back({2, 3});
  101.  
  102.     graph[1].push_back({2, 1});
  103.     graph[1].push_back({3, 2});
  104.  
  105.     graph[2].push_back({3, 4});
  106.  
  107.     graph[3].push_back({4, 2});
  108.  
  109. }
  110.  
  111. int main() {
  112.  
  113.     vector<int> parent(N, -1); // stores the parent of each node in the MST
  114.     vector<int> key(N, INF); // stores the minimum weight to reach each node
  115.     vector<bool> inMST(N, false); // indicates whether a node is already in the MST
  116.     int source = 0; // source node
  117.  
  118.     initializeGraph();
  119.  
  120.     primMST(source, key, parent, inMST);
  121.  
  122.     printMST(key, parent);
  123.  
  124.     return 0;
  125. }
  126.  
Success #stdin #stdout 0.01s 5296KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Iteration 1:
weight: 4
edge: 0 - 1
Key values: 0, 4, INF, INF, INF, 
Parent values: -1, 0, -1, -1, -1, 

Iteration 2:
weight: 3
edge: 0 - 2
Key values: 0, 4, 3, INF, INF, 
Parent values: -1, 0, 0, -1, -1, 

Iteration 3:
weight: 4
edge: 2 - 3
Key values: 0, 4, 3, 4, INF, 
Parent values: -1, 0, 0, 2, -1, 

Iteration 4:
weight: 2
edge: 1 - 3
Key values: 0, 4, 3, 2, INF, 
Parent values: -1, 0, 0, 1, -1, 

Iteration 5:
weight: 2
edge: 3 - 4
Key values: 0, 4, 3, 2, 2, 
Parent values: -1, 0, 0, 1, 3, 

Minimum Spanning Tree Edges:

Edge 	Weight
0 - 1	4
0 - 2	3
1 - 3	2
3 - 4	2
https://ideone.com/5CuIRn
language:
C++ 4.3.2 (gcc-4.3.2)
created:
279 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!