The Algorithm Design Manual Second Edition

Analysis

Prim’s algorithm is correct, but how efficient is it? This depends on which data

structures are used to implement it. In the pseudocode, Prim’s algorithm makes

n iterations sweeping through all m edges on each iteration—yielding an O(mn)

algorithm.

But our implementation avoids the need to test all m edges on each pass. It

only considers the

≤ n cheapest known edges represented in the parent array

and the

≤ n edges out of new tree vertex v to update parent. By maintaining a

Boolean flag along with each vertex to denote whether it is in the tree or not, we

test whether the current edge joins a tree with a non-tree vertex in constant time.

The result is an O(n

2

) implementation of Prim’s algorithm, and a good illustra-

tion of power of data structures to speed up algorithms. In fact, more sophisticated

---

196

6 .

W E I G H T E D G R A P H A L G O R I T H M S

6

Kruskal(G)

Prim(G,A)

G

3

A

2

3

4

1

5

A

4

2

6

5

1

A

2

5

4

3

7

12

7

4

7

2

9

5

Figure 6.3: A graph G (l) with minimum spanning trees produced by Prim’s (m) and Kruskal’s

(r) algorithms. The numbers on the trees denote the order of insertion; ties are broken arbi-

trarily

priority-queue data structures lead to an O(m + n lg n) implementation, by making

it faster to find the minimum cost edge to expand the tree at each iteration.

The minimum spanning tree itself or its cost can be reconstructed in two dif-

ferent ways. The simplest method would be to augment this procedure with state-

ments that print the edges as they are found or totals the weight of all selected

edges. Alternately, the tree topology is encoded by the parent array, so it plus the

original graph describe everything about the minimum spanning tree.