Kruskal and Prim MST Algorithms

Two classical greedy algorithms—Kruskal's and Prim's—efficiently compute minimum spanning trees by exploiting the cut and cycle properties. Both achieve optimal $O(m \log n)$ time complexity with appropriate data structures.

TheoremKruskal's Algorithm Correctness

Kruskal's algorithm produces a minimum spanning tree: sort edges by weight and add edges that don't create cycles (using union-find).

Proof: By induction on edges added. Each edge $e$ added connects two components. By the cut property, the minimum-weight edge crossing this cut belongs to some MST. Since $e$ is the minimum-weight available edge not creating a cycle, it satisfies this condition.

DefinitionKruskal's Algorithm

MST-Kruskal(G, w):
  Sort edges E by weight: e₁, e₂, ..., eₘ
  Initialize: T = ∅, UnionFind UF with n components
  For each edge e = {u,v} in sorted order:
    If UF.Find(u) ≠ UF.Find(v):
      T = T ∪ {e}
      UF.Union(u, v)
  Return T

Time: $O(m \log m) = O(m \log n)$ for sorting plus $O(m \alpha(n))$ for union-find operations, where $\alpha$ is the inverse Ackermann function.

TheoremPrim's Algorithm Correctness

Prim's algorithm produces a minimum spanning tree: start from arbitrary vertex and repeatedly add minimum-weight edge connecting the tree to a new vertex.

Proof: Maintain invariant that edges selected form a tree. At each step, the minimum-weight edge crossing the cut $(S, V \setminus S)$ where $S$ is the current tree must be in some MST by the cut property.

DefinitionPrim's Algorithm

MST-Prim(G, w, r):
  Initialize: S = {r}, T = ∅, PriorityQueue Q
  For each v ∈ V \ {r}: Q.insert(v, key = ∞)
  For each neighbor u of r: Q.decreaseKey(u, w(r,u))

  While Q not empty:
    v = Q.extractMin()
    Add edge connecting v to S to T
    S = S ∪ {v}
    For each neighbor u of v not in S:
      If w(v,u) < Q.key(u):
        Q.decreaseKey(u, w(v,u))
  Return T

Time: $O(m \log n)$ using binary heap, $O(m + n \log n)$ using Fibonacci heap.

ExampleAlgorithm Comparison

For a graph with 6 vertices and weighted edges forming a grid, Kruskal processes edges globally (1→2→3→...), while Prim grows locally from a starting vertex. Both produce the same MST weight but may select different edge sets if ties exist.

Kruskal is preferred for sparse graphs (small $m$ ) and works naturally with sorted edge lists. Prim excels for dense graphs and when starting from a specific vertex matters.

Remark

Reverse-delete algorithm is another MST approach: consider edges in decreasing weight order and delete edges that don't disconnect the graph. This maintains the cycle property: the heaviest edge in any cycle isn't in an MST. Though conceptually elegant, it's less efficient than Kruskal or Prim.

Both algorithms demonstrate the power of greedy approaches when problems have optimal substructure and the greedy choice property, fundamental concepts in algorithm design and optimization.