Kruskal's algorithm builds a Minimum Spanning Tree by sorting all edges by weight and adding each edge if it doesn't create a cycle. Cycle detection is done efficiently with a Union-Find (Disjoint Set Union) data structure. Total time complexity is O(E log E) dominated by the sort.
struct DSU{vector<int>p,r;DSU(int n):p(n),r(n,0){iota(p.begin(),p.end(),0);}
int find(int x){return p[x]==x?x:p[x]=find(p[x]);}
bool unite(int a,int b){a=find(a);b=find(b);if(a==b)return false;
if(r[a]<r[b])swap(a,b);p[b]=a;if(r[a]==r[b])r[a]++;return true;}};
int kruskal(int n,vector<tuple<int,int,int>>edges){
sort(edges.begin(),edges.end());
DSU dsu(n);int total=0;
for(auto[w,u,v]:edges) if(dsu.unite(u,v)) total+=w;
return total;
}Kruskal's sorts all edges by weight ascending. It then iterates through them, adding each edge to the MST if it doesn't form a cycle. This greedy approach produces the optimal MST.
Each vertex starts in its own set. When adding edge (u,v), check if u and v are in the same set (would form a cycle). If not, union their sets and add the edge. Find uses path compression for near O(1) queries.
Kruskal's is O(E log E) for sparse graphs. Prim's with a heap is O(E log V). For very dense graphs (E ≈ V²), Prim's wins. For sparse graphs, both are equivalent.
Quiz coming soon for this algorithm.