A spanning tree connects every vertex of a graph using the fewest edges (V−1) with no cycles. The minimum spanning tree (MST) is the spanning tree with the smallest total edge weight. Kruskal's algorithm sorts edges by weight and adds each edge unless it would create a cycle — a decision tracked with a union-find structure.
Kruskal's minimum spanning tree algorithmSort edges by weight ascending
For each edge (u, v):
if u and v are not yet connected → add edge to MST
else → skip (would form a cycle)
Stop when V−1 edges are chosen
Total weight of the resulting tree is minimal.
Cycle detection
Two vertices already connected through earlier MST edges must not be joined again — that would create a cycle. Union-find answers 'are these two connected?' in near-constant time, which is why Kruskal runs in O(E log E).