The Algorithm Design Manual Second Edition

6.1

Minimum Spanning Trees

A spanning tree of a graph G = (V, E) is a subset of edges from E forming a

tree connecting all vertices of V . For edge-weighted graphs, we are particularly

interested in the minimum spanning tree—the spanning tree whose sum of edge

weights is as small as possible.

Minimum spanning trees are the answer whenever we need to connect a set

of points (representing cities, homes, junctions, or other locations) by the smallest

amount of roadway, wire, or pipe. Any tree is the smallest possible connected graph

in terms of number of edges, while the minimum spanning tree is the smallest

connected graph in terms of edge weight. In geometric problems, the point set

p

1

, . . . , p

n

defines a complete graph, with edge (v

i

, v

j

) assigned a weight equal to

the distance from p

i

to p

j

. An example of a geometric minimum spanning tree is

illustrated in Figure

6.1

. Additional applications of minimum spanning trees are

discussed in Section

15.3

(page

484

).

A minimum spanning tree minimizes the total length over all possible spanning

trees. However, there can be more than one minimum spanning tree in a graph.

Indeed, all spanning trees of an unweighted (or equally weighted) graph G are

minimum spanning trees, since each contains exactly n

− 1 equal-weight edges.

Such a spanning tree can be found using depth-first or breadth-first search. Finding

a minimum spanning tree is more difficult for general weighted graphs, however

two different algorithms are presented below. Both demonstrate the optimality of

certain greedy heuristics.