Growing A Minimum Spanning Tree

Growing a minimum spanning tree: Assume that we have a connected, undirected graph G = (V, E) with a weight function w : E → R, and we 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 of edges A, maintaining the following loop invariant:

Prior to each iteration, A is a subset of some minimum spanning tree.

At each step, we determine an edge (u, v) 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 while maintaining 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

We use the loop invariant as follows:

Initialization: After line 1, the set A trivially satisfies the loop invariant.
Maintenance: The loop in lines 2-4 maintains the invariant by adding only safe edges.
Termination: All edges added to A are in a minimum spanning tree, and so the set A is returned in line 5 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. Within the while loop body, A must be a proper subset of T, and therefore there must be an edge (u, v) ∈ T such that (u, v) ∉ A and (u, v) is safe for A.

In the remainder of this section, we provide a rule for recognizing safe edges. The The algorithms of Kruskal and Prim describes two algorithms that use this rule to find safe edges efficiently.

We first need some definitions. A cut (S, V - S) of an undirected graph G = (V, E) is a partition of V. Figure 23.2 illustrates this notion. We say that an edge (u, v) ∈ E crosses the cut (S, V - S) if one of its endpoints is in S and the other is in V - S. We say that a cut respects a set A of edges if no edge in A crosses the cut. An edge is a light edge crossing a cut if its weight is the minimum of any edge crossing the cut. Note that there can be more than one light edge crossing a cut in the case of ties. More generally, we say that an edge is a light edge satisfying a given property if its weight is the minimum of any edge satisfying the property.

Figure 23.2: Two ways of viewing a cut (S, V - S) of the graph from Figure 23.1. (a) The vertices in the set S are shown in black, and those in V - S are shown in white. The edges crossing the cut are those connecting white vertices with black vertices. The edge (d, c) is the unique light edge crossing the cut. A subset A of the edges is shaded; note that the cut (S, V - S) respects A, since no edge of A crosses the cut. (b) The same graph with the vertices in the set S on the left and the vertices in the set V - S on the right. An edge crosses the cut if it connects a vertex on the left with a vertex on the right

SKEDSOFT