# Kruskal's Algorithm — Minimum Spanning Tree (C++) ## Introduction Kruskal builds a Minimum Spanning Tree (MST) by sorting all edges by weight and adding edges in ascending order if they do not create a cycle. Cycle detection is efficiently implemented with a Disjoint Set Union (Union-Find). ## Steps 1. Sort edges by weight. 2. Iterate edges; for each `(u,v,w)`, if `find(u) != find(v)` then union them and include edge in MST. 3. Continue until MST contains `V-1` edges. ## Complexity - Sorting: **O(E log E)** - Union-Find operations: ~**O(E α(V))** (α is inverse-Ackermann) - Overall: **O(E log E)** ## Reference implementation notes File: `https://github.com/mashrur-rahman-fahim/algorithm/blob/main/Kruskal.cpp` The repo uses a `find` helper (recursive). For production, ensure path compression & union by rank/size for efficiency. ### Minimal pseudo-snippet ```cpp\nsort(edges.begin(), edges.end()); // by weight for (edge : edges) { if (find(edge.u) != find(edge.v)) { union(edge.u, edge.v); mst.push_back(edge); cost += edge.w; } }\n``` ## Pitfalls - If `find` lacks path compression, performance degrades for large graphs. - Input indexing differences (0 vs 1 based) — normalize. ## Source `https: //github.com/mashrur-rahman-fahim/algorithm/blob/main/Kruskal.cpp`