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>& parent, vector<int>& key) {
  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) {
  48.     vector<int> parent(N, -1); // stores the parent of each node in the MST
  49.     vector<int> key(N, INF); // stores the minimum weight to reach each node
  50.     vector<bool> inMST(N, false); // indicates whether a node is already in the MST
  51.     int i = 1;
  52.  
  53.     // Custom comparator for the priority queue
  54.     auto cmp = [](const graphNode& a, const graphNode& b) {
  55.         return a.second > b.second;
  56.     };
  57.  
  58.     priority_queue<graphNode, vector<graphNode>, decltype(cmp)> pq(cmp);
  59.  
  60.     key[source] = 0; // Start with the source node
  61.     pq.push({source, key[source]});
  62.  
  63.     while (!pq.empty()) {
  64.         int u = pq.top().first;
  65.         pq.pop();
  66.  
  67.         inMST[u] = true;
  68.  
  69.         for (auto edge : graph[u]) {
  70.             int v = edge.first;
  71.             int weight = edge.second;
  72.  
  73.             if (!inMST[v] && weight < key[v]) {
  74.                 parent[v] = u;
  75.                 key[v] = weight;
  76.                 pq.push({v, key[v]});
  77.  
  78.                 cout<<"Iteration "<<i++<<":"<<endl;
  79.  
  80.                 cout<<"weight: "<<weight<<endl;
  81.                 cout<<"edge: "<<u<<" - "<<v<<endl;
  82.  
  83.                 cout<<"Key values: ";
  84.                 printVector(key);
  85.  
  86.                 cout<<"Parent values: ";
  87.                 printVector(parent);
  88.                 cout<<endl;
  89.  
  90.             }
  91.         }
  92.     }
  93.  
  94.     printMST(parent, key);
  95. }
  96.  
  97. void initializeGraph() {
  98.  
  99.     // Example graph
  100.     // pair {node, weight}
  101.     graph[0].push_back({1, 4});
  102.     graph[0].push_back({2, 3});
  103.  
  104.     graph[1].push_back({2, 1});
  105.     graph[1].push_back({3, 2});
  106.  
  107.     graph[2].push_back({3, 4});
  108.  
  109.     graph[3].push_back({4, 2});
  110.  
  111. }
  112.  
  113. int main() {
  114.     int source = 0; // source node
  115.     initializeGraph();
  116.  
  117.     primMST(source);
  118.  
  119.     return 0;
  120. }
Success #stdin #stdout 0.01s 5520KB
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/nxD8Tz
language:
C++14 (gcc 8.3)
created:
2 years 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!