In the design of electronic circuitry, it is often necessary to make the pins of several components electrically equivalent by wiring them together. To interconnect a set of *n* pins, we can use an arrangement of *n -* 1 wires, each connecting two pins. Of all such arrangements, the one that uses the least amount of wire is usually the most desirable.

We can model this wiring problem with a connected, undirected graph *G* = (*V, E*), where *V* is the set of pins, *E* is the set of possible interconnections between pairs of pins, and for each edge (*u, v*) *E*, we have a weight *w*(*u*, *v*) specifying the cost (amount of wire needed) to connect *u* and *v*. We then wish to find an acyclic subset *T* *E* that connects all of the vertices and whose total weight

The two algorithms also illustrate a heuristic for optimization called the "greedy" strategy. At each step of an algorithm, one of several possible choices must be made. The greedy strategy advocates making the choice that is the best at the moment. Such a strategy is not generally guaranteed to find globally optimal solutions to problems. For the minimum-spanning-tree problem, however, we can prove that certain greedy strategies do yield a spanning tree with minimum weight. Greedy strategies are discussed at length in Chapter 17. Although the present chapter can be read independently of Chapter 17, the greedy methods presented here are a classic application of the theoretical notions introduced there.

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

GENERIC-MST(G, w)

1A

2whileAdoes not form a spanning tree

3dofind an edge (u, v) that is safe forA

4AA{(u, v)}

5returnA

We first need some definitions. A * cut* (

Our rule for recognizing safe edges is given by the following theorem.

w(T') = w (T) - w(x, y) + w(u,v)

w (T) .

But *T* is a minimum spanning tree, so that *w*(*T*) *w*(*T*'*); thus, *T*'* must be a minimum spanning tree also.

The two algorithms in Section 24.2 use the following corollary to Theorem 24.1.

* Proof *The cut (

Kruskal's algorithm is based directly on the generic minimum-spanning-tree algorithm given in Section 24.1. It finds a safe edge to add to the growing forest by finding, of all the edges that connect any two trees in the forest, an edge (*u*, *v*) of least weight. Let *C*_{1} and *C*_{2} denote the two trees that are connected by (*u*, *v*). Since (*u*,*v*) must be a light edge connecting *C*_{1} to some other tree, Corollary 24.2 implies that (*u*, *v*) is a safe edge for *C*_{1}. Kruskal's algorithm is a greedy algorithm, because at each step it adds to the forest an edge of least possible weight.

MST-KRUSKAL(G,w)

1A

2foreach vertexvV[G]

3doMAKE-SET (v)

4 sort the edges ofEby nondecreasing weightw

5foreach edge (u,v)E, in order by nondecreasing weight

6doif FIND-SET(u) FIND-SET(v)

7thenAA{(u,v)}

8 UNION (u,v)

9returnA

Like Kruskal's algorithm, Prim's algorithm is a special case of the generic minimum-spanning-tree algorithm from Section 24.1. Prim's algorithm operates much like Dijkstra's algorithm for finding shortest paths in a graph. (See Section 25.2.) Prim's algorithm has the property that the edges in the set *A* always form a single tree. As is illustrated in Figure 24.5, the tree starts from an arbitrary root vertex *r* and grows until the tree spans all the vertices in *V*. At each step, a light edge connecting a vertex in *A* to a vertex in *V* - *A* is added to the tree. By Corollary 24.2, this rule adds only edges that are safe for *A*; therefore, when the algorithm terminates, the edges in *A* form a minimum spanning tree. This strategy is "greedy" since the tree is augmented at each step with an edge that contributes the minimum amount possible to the tree's weight.

The key to implementing Prim's algorithm efficiently is to make it easy to select a new edge to be added to the tree formed by the edges in *A*. In the pseudocode below, the connected graph *G* and the root *r* of the minimum spanning tree to be grown are inputs to the algorithm. During execution of the algorithm, all vertices that are *not* in the tree reside in a priority queue *Q* based on a *key* field. For each vertex *v*, *key*[*v*] is the minimum weight of any edge connecting *v* to a vertex in the tree; by convention, *key*[*v*] = if there is no such edge. The field [*v*] names the "parent" of *v* in the tree. During the algorithm, the set *A* from GENERIC-MST is kept implicitly as

A= {(v, [v]) :vV- {r} -Q} .

A= {(v, [v]) :vV- {r}} .

MST-PRIM(G, w, r)

1QV[G]

2foreachuQ

3dokey[u]

4key[r] 0

5[r] NIL

6whileQ

7douEXTRACT-MIN(Q)

8foreachvAdj[u]

9doifvQandw(u,v) <key[v]

10then[v]u

11key[v]w(u,v)

Prim's algorithm works as shown in Figure 24.5. Lines 1-4 initialize the priority queue *Q* to contain all the vertices and set the key of each vertex to , except for the root *r*, whose key is set to 0. Line 5 initializes [*r*] to NIL, since the root *r* has no parent. Throughout the algorithm, the set *V - Q* contains the vertices in the tree being grown. Line 7 identifies a vertex *u ** Q* incident on a light edge crossing the cut (*V - Q, Q*) (with the exception of the first iteration, in which *u* = *r* due to line 4). Removing *u *from the set *Q* adds it to the set *V - Q* of vertices in the tree. Lines 8-11 update the *key* and fields of every vertex *v* adjacent to *u* but not in the tree. The updating maintains the invariants that *key*[*v*] = *w*(*v*,* *[*v*]) and that (*v*,* *[*v*]) is a light edge connecting *v* to some vertex in the tree.

The performance of Prim's algorithm depends on how we implement the priority queue *Q*. If *Q* is implemented as a binary heap (see Chapter 7), we can use the BUILD-HEAP procedure to perform the initialization in lines 1-4 in *O*(*V*) time. The loop is executed |*V|* times, and since each EXTRACT-MIN operation takes *O*(lg *V*) time, the total time for all calls to EXTRACT-MIN is *O*(*V* 1g *V*). The **for** loop in lines 8-11 is executed *O*(*E*) times altogether, since the sum of the lengths of all adjacency lists is 2 |*E*|. Within the **for** loop, the test for membership in *Q* in line 9 can be implemented in constant time by keeping a bit for each vertex that tells whether or not it is in *Q*, and updating the bit when the vertex is removed from *Q*. The assignment in line 11 involves an implicit DECREASE-KEY operation on the heap, which can be implemented in a binary heap in *O*(lg *V*) time. Thus, the total time for Prim's algorithm is *O*(*V *1g *V *+ *E *1g *V*) = *O*(*E *lg *V*), which is asymptotically the same as for our implementation of Kruskal's algorithm.

The asymptotic running time of Prim's algorithm can be improved, however, by using Fibonacci heaps. Chapter 21 shows that if |*V*| elements are organized into a Fibonacci heap, we can perform an EXTRACT-MIN operation in *O*(lg *V*) amortized time and a DECREASE-KEY operation (to implement line 11) in *O*(1) amortized time. Therefore, if we use a Fibonacci heap to implement the priority queue *Q*, the running time of Prim's algorithm improves to *O*(*E + V* 1g *V*).

Kruskal's algorithm can return different spanning trees for the same input graph *G*, depending on how ties are broken when the edges are sorted into order. Show that for each minimum spanning tree *T* of *G*, there is a way to sort the edges of *G* in Kruskal's algorithm so that the algorithm returns *T*.

Suppose that the graph *G* = (*V, E*) is represented as an adjacency matrix. Give a simple implementation of Prim's algorithm for this case that runs in *O*(*V*^{2}) time.

Suppose that all edge weights in a graph are integers in the range from 1 to |*V*|. How fast can you make Kruskal's algorithm run? What if the edge weights are integers in the range from 1 to *W* for some constant *W*?

Suppose that all edge weights in a graph are integers in the range from 1 to |*V*|. How fast can you make Prim's algorithm run? What if the edge weights are integers in the range from 1 to *W* for some constant *W*?

24-1 Second-best minimum spanning tree

Let *G = *(*V, E*) be an undirected, connected graph with weight function *w *: *E* **R**, and suppose that |*E| * |*V| .*

* c.* Give an efficient algorithm to compute the second-best minimum spanning tree of

24-2 Minimum spanning tree in sparse graphs

For a very sparse connected graph* G* = (*V, E*), we can improve upon the *O*(*E *+ *V *lg *V*) running time of Prim's algorithm with Fibonacci heaps by "preprocessing" *G* to decrease the number of vertices before running Prim's algorithm. The following procedure takes as input a weighted graph *G* and returns a "contracted" version of *G*, having added some edges to the minimum spanning tree *T* under construction. Initially, for each edge (*u, v*) * E*, we assume that *orig*[*u, v*] = (*u, v*) and that *w*[*u, v*] is the weight of the edge.

MST-REDUCE(G, T)

1foreachvV[G]

2domark[v] FALSE

3 MAKE-SET(v)

4foreachuV[G]

5do ifmark[u] = FALSE

6thenchoosevAdj[u] such thatw[u, v] is minimized

7 UNION(u,v)

8TT{orig[u, v]}

9mark[u]mark[v] TRUE

10V[G'] {FIND-SET(v) :vV[G]}

11E[G']

12foreach (x, y)E[G]

13douFIND-SET(x)

14vFIND-SET(y)

15if(u, v)E[G']

16thenE[G']E[G'] {(u, v)}

17orig[u, v]orig[x, y]

18w[u, v]w[x, y]

19else ifw[x, y] <w[u, v]

20thenorig[u, v]orig[x, y]

21w[u, v]w[x, y]

22 construct adjacency listsAdjforG'

23returnG' andT