Cây khung nhỏ nhất - Thuật toán Prim

Cây khung nhỏ nhất - Thuật toán Prim

Độ phức tạp: O(E * logV)


#include <bits/stdc++.h>
using namespace std;

const int INT_MAX = 1e9; typedef pair<int, int> pii;

// input
vector<vector<pii> > adj;

// output
vector<int> pre;


long long Prim() {
  int n = adj.size();
  pre.assign(n, -1);
  vector<bool> visited(n);
  vector<int> dist(n, INT_MAX);
  dist[0] = 0;

  priority_queue<pii, vector<pii> , greater<pii> > q;
  q.push(make_pair(0, 0));

  long long res = 0;

  while (!q.empty()) {
    int d = q.top().first;
    int u = q.top().second;
    q.pop();
    
    if (visited[u]) continue;

    visited[u] = true;
    res += d;

    for (int i = 0; i < (int) adj[u].size(); i++) {
      int v = adj[u][i].first;

      if (visited[v]) continue;

      int nprio = g[u][i].second;
      if (dist[v] > nprio) {
        dist[v] = nprio;
        pred[v] = u;
        q.push(make_pair(nprio, v));
      }
    }
  }

  return res;
}


int main() {
  adj.resize(3);
  adj[0].push_back(make_pair(1, 10));
  adj[1].push_back(make_pair(0, 10));
  adj[1].push_back(make_pair(2, 10));
  adj[2].push_back(make_pair(1, 10));
  adj[2].push_back(make_pair(0, 5));
  adj[0].push_back(make_pair(2, 5));

  long long res = Prim();
  cout << res << endl;
}