MST

The minimum spanning tree problem is one of the most famous in Graph Theory. It is as follows: Given a weighted undirected graph, find any spanning tree with minimum sum of edge weights. A spanning tree is any subset of edges that forms a tree and contains every single vertex in the original graph. 

Kruskal’s

Kruskal’s algorithm finds the MST by using a greedy method. Firstly, we sort the edges in increasing order of edge weights. Then we iterate over them while simultaneously maintaining a Disjoint Set Union to track connectivity. At any edge, if the 2 nodes are already connected then we skip this edge, otherwise we add this edge to the answer and merge the 2 nodes. At the end we should end up with the minimum spanning tree. 

struct Edge{
    int u, v, w; //u, v are nodes and  w is the weight
};
struct DSU{
vector<int> par, sz;
int N;
DSU(int n){
N = n; par.resize(N+1);
sz.resize(N+1);
iota(par.begin(), par.end(), 0);
fill(sz.begin(), sz.end(), 1);
}
int fnd(int src){return par[src] == src ? par[src]: fnd(par[src]);}
bool merge(int a, int b){
a = fnd(a); b= fnd(b);
if(a==b)return 0;
if(sz[a] < sz[b])swap(a, b);
sz[a] += sz[b];
par[b] = a;
return 1;
}
int get_sz(int u){
return sz[fnd(u)];
}
};

bool comp(Edge &a, Edge &b){
    return a.w < b.w;
}
int kruskal(vector<Edge> edges, int N){
    DSU ds(N+1);
    int ans = 0;
    sort(edges.begin(), edges.end(), comp); //sorted edges
    for(Edge e : edges){
        if(ds.fnd(e.u) == ds.fnd(e.v))continue; //same component, ignore
        ans += e.w; ds.merge(e.u, e.v);  //add to MST
    }
    return ans;
}

Other MST algorithms include:

  • Prims (Dijkstra-esque algorithm)
  • Boruvka’s Algorithm