Growing a minimum spanning tree

Assume that we have a connected, undirected graph G = (V, E) with a weight function w : E R and wish to find a minimum spanning tree for G. The two algorithms we consider in this chapter use a greedy approach to the problem, although they differ in how they apply this approach.

This greedy strategy is captured by the following "generic" algorithm, which grows the minimum spanning tree one edge at a time. The algorithm manages a set A that is always a subset of some minimum spanning tree. At each step, an edge (u, v) is determined that can be added to A without violating this invariant, in the sense that A {(u, v)} is also a subset of a minimum spanning tree. We call such an edge a safe edge for A, since it can be safely added to A without destroying the invariant.

GENERIC−MST(G, w)

1 A

2 while A does not form a spanning tree

3 do find an edge (u, v) that is safe for A

4 A <- A {(u, v)}

5 return A

Note that after line 1, the set A trivially satisfies the invariant that it is a subset of a minimum spanning tree.

The loop in lines 2−4 maintains the invariant. When the set A is returned in line 5, therefore, it must be a minimum spanning tree.

The tricky part is, of course, finding a safe edge in line 3. One must exist, since when line 3 is executed, the invariant dictates that there is a spanning tree T such that A T, and if there is an edge (u,v) T such that (u, v) A, then (u, v) is safe for A.