Advanced High-School Mathematics

130 CHAPTER 2 Discrete Mathematics

tained a lower bound for the total weight of a minimal-weight

Hamiltonian cycle.

(b) (Upper bound)Use one of the efficient methods above (Nearest-

neighbor or cheapest-link algorithm) to find a Hamiltonian

cycle. The weight is then an upper bound.

Prim’s algorithm

Like Kruskal’s algorithm, Prim’s algorithm is an efficient method
for finding a minimal-weight spanning tree in a weighted graph. We
describe this as follows. Assume that the given weighted graph isG.
For convenience, we shall initially regard all of the vertices and edges
inGas colored black.

Step 1. Pick an initial vertexv 1. Color this vertex red.

Step 2. Find a vertexv 2 of minimal distance (weight) tov 1. Color

the vertexv 2 and the edge{v 1 ,v 2 }red.

Step 3. Choose a new vertexv 3 of minimal distance to eitherv 1 or

v 2. Color the new vertexv 3 and the corresponding minimal-length

edge red.

Stepn. Repeated application of the above will determine a red sub-

tree ofGwith verticesv 1 , v 2 , ...,vn− 1. Find a black edge of mini-

mal weight on one of the aboven−1 vertices. Color this edge and

the new vertexvn which it determines red.

Conclusion. Continue until all vertices inGhave been colored red;

the resulting red graph is a minimal-weight spanning tree.

Exercises

1. Use Prim’s algorithm to find minimal spanning trees in the first
   two exercises on page 129.