Minimum Spanning Tree ( Prim's Algo)

primsAlgoEfficient.cpp

#include "./../my_lib.h"
vector<pair<int, int>> adj[100005];

void primsBrute(int V) {
  vector<int> key(V, INT_MAX);
  vector<int> parent(V, -1);
  vector<bool> MST(V, false);

  key[0] = 0;
  parent[0] = -1;

  priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> PQ;

  PQ.push({ 0, 0 });

  while (!PQ.empty()) {
    int u = PQ.top().second; PQ.pop();

    MST[u] = true;

    for (auto it : adj[u]) {
      int v = it.first;
      int w = it.second;
      if (MST[v] == false && w < key[v]) {
        key[v] = w;
        parent[v] = u;
        PQ.push({ key[v], v });
      }
    }
  }

  cout << "{ u, v, w } " << endl;
  for (int i = 1; i < V; i++) {
    cout << "{ " << i << ", " << parent[i] << ", " << key[i] << " }" << endl;
  }
}

int main() {
  int V, m;
  cin >> V >> m;
  int a, b, w;

  for (int i = 1; i <= m; i++) {
    cin >> a >> b >> w;
    adj[a].push_back({ b, w });
    adj[b].push_back({ a, w });
  }

  primsBrute(V);
}

/*
Input:
5
6
0 1 2
0 3 6
1 3 8
1 4 5
1 2 3
2 4 7

Output:
{ u, v, w } 
{ 1, 0, 2 }
{ 2, 1, 3 }
{ 3, 0, 6 }
{ 4, 1, 5 } 
*/