Chapter 23: Minimum Spanning Trees

Thomas H. Cormen, Charles E. Leiserson, Ronald Rivest, Clifford Stein. Introduction to Algorithms, Second Edition. The MIT Press, 2001

Solving the minimum-spanning-tree problem.

A minimum-weight spanning tree (MST) is

an acyclic subset $T \subseteq E$ that connects all of the vertices and whose total weight is minimized.

23.2 The Algorithms of Kruskal and Prim

Kruskal's and Prim's are greedy algorithms. At each step, they add the lightest safe edge to the MST. A safe edge connects two previously unconnected subtrees of the final MST.

Kruskal's Algorithm:

For each edge in nondecreasing order by weight, Kruskal's adds that edge to the MST if it joins two current subtrees of the MST. Kruskal's runs in $O(ElgV)$ time if it uses an optimal disjoint-set-forest implementation.

MST-KRUSKAL($G$, $w$)

1. $A \larr \emptyset$
2. create $|V|$ trees, one containing each vertex
3. sort the edges of $E$ into nondecreasing order by weight $w$
4. for each edge $(u,v)$ $\epsilon$ $E$, taken in nondecreasing order by weight
5. $\qquad$do if $u$ and $v$ are not in the same set
6. $\qquad\qquad$then $A \larr A \cup \{(u,v)\}$
7. $\qquad\qquad\qquad$join the sets that contain $u$ and $v$
8. return $A$

Prim's Algorithm:

Prim's starts at the root, $r$, and adds the lightest edge connected to the current MST. As each edge is considered, any neighbors that aren't already in the MST are relaxed. Prim's runs in $O(E+VlgV)$ with a Fibonacci heap or slower, in $O(ElgV)$, with a binary min-heap.

MST-PRIM($G$, $w$, $r$)

1. [ initialize $key[u]=\infty$ and $\pi[u]=nil$ for every $u$ $\epsilon$ $V[G]$ ]
2. $key[r] \larr 0$
3. $Q \larr V[G]$
4. while $Q \neq \emptyset$
5. $\qquad$do $u \larr \text{EXTRACT-MIN}(Q)$
6. $\qquad\qquad$for each $v$ $\epsilon$ $Adj[u]$
7. $\qquad\qquad\qquad$do if $v$ $\epsilon$ $Q$ and $w(u,v) \lt key[v]$
8. $\qquad\qquad\qquad\qquad$then $\pi[v] \larr u$
9. $\qquad\qquad\qquad\qquad\qquad key[v] \larr w(u,v)$
10. [ $\pi$ is a parent function that contains the MST ]