Minimum Spanning Tree

In this article we will mainly be talking about Prim's algorithm and also a bit of Union Find.

Idea

There is two sorts of minimum spanning tree algorithm : Kruskal (Union-Find) and Prim (Greedy Algorithm). The two algorithm have the same complexity. Here is a two small illustrations so you could see the idea of the two algorithm.

Kruskal

Loads of people prefer Kruskal then Prim but I prefer Prim. Kruskal uses the Union Find algorithm. Union Find algorithm is a graph algorithm who uses a getcomp function to see if getcomp(a) == getcomp(b). If it does then a and b are in the same component. Else comp[getcomp(a)] = getcomp(b). Here is the function getcomp in C++:

int getcomp(vector& comp,int a){
   int compa=comp[a];
   while (compa != comp[compa]){
      compa = comp[compa];
   }
   comp[a] = compa;
   return compa;
}

C++ Code - Prim

#include <iostream>
#include <vector>
#include <queue>
#include <set>
using namespace std;
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N,A,L,K1,K2,ret=0;
    cin >> N >> A;
    vector<vector<pair<int,int>>> adj(N+1);
    for (int i=0; i<A; ++i){       cin >> K1 >> K2 >> L;
       adj[K1].emplace_back(L,K2);
       adj[K2].emplace_back(L,K1);
    }
    vector<int> vu(N+1);
    vu[1]=1;
    set<pair<int,int>> s;
    for (auto& i:adj[1]) s.emplace(i);
    while (!s.empty()){
       auto f=*s.begin();
       s.erase(s.begin());
       if (vu[f.second]) continue;
       ret += f.first;
       vu[f.second]=1;
       for (auto& i:adj[f.second]){
          if (!vu[i.second]) s.emplace(i);
       }
    }
    cout << ret;
    return 0;
}