Minimum Cost Spanning Tree & Kruskal's Algorithm

Definition

For connected undirected weighted graph $G(V,E,w)$, a spanning tree is acyclic connected subgraph spanning all $V$ with $|V|-1$ edges. Minimum Cost Spanning Tree (MST) / Minimum Spanning Tree is spanning tree minimizing $\sum_{e\in T} w(e)$. If distinct weights, MST unique; otherwise multiple. Cut property and cycle property characterize MST.

Kruskal's Algorithm (Greedy)

Kruskal(G):
  T=∅
  sort E by weight ascending
  make Union-Find structure for V
  for (u,v) in sorted E:
    if Find(u) != Find(v):
      T.add((u,v))
      Union(u,v)
      if |T|==|V|-1: break
  return T

Correctness via cut property: smallest edge crossing any cut belongs to some MST; cycle property prevents adding cycle edge.

Complexities: Sorting $O(E\log E)$, Union-Find $O(E \alpha(V))$ → total $O(E\log E)$ ($\alpha$ inverse Ackermann). Space $O(V)$.

Example

Graph: $V=\{A,B,C,D\}$, edges: AB1, AC3, BC3, BD4, CD2

• Sorted: AB1, CD2, AC3, BC3, BD4
• Add AB1 (A|B), add CD2 (C|D), add AC3 (merges {A,B} with {C,D} → {A,B,C,D}), skip BC3 (would cycle A-B-C), skip BD4. MST weight 1+2+3=6 edges AB,CD,AC.

Kruskal vs Prim

• Kruskal edge-based, good for sparse graphs; Prim vertex-based, good for dense ($O(E\log V)$ with heap, $O(V^2)$ naive).
• Both optimal, choice depends on density and structure.