Java Reference
In-Depth Information
Prim's algorithm is an example of a greedy algorithm. At each step in the
for
loop, we select the least-cost edge that connects some marked vertex to some
unmarked vertex. The algorithm does not otherwise check that the MST really
should include this least-cost edge. This leads to an important question: Does
Prim's algorithm work correctly? Clearly it generates a spanning tree (because
each pass through the
for
loop adds one edge and one unmarked vertex to the
spanning tree until all vertices have been added), but does this tree have minimum
cost?
Theorem11.1
Prim's algorithm produces a minimum-cost spanning tree.
Proof:
We will use a proof by contradiction. Let G = (V; E) be a graph for which
Prim's algorithm does not generate an MST. Define an ordering on the vertices
according to the order in which they were added by Prim's algorithm to the MST:
v
0
; v
1
;:::; v
n1
. Let edge e
i
connect (v
x
, v
i
) for some x < i and i 1. Let e
j
be the
lowest numbered (first) edge added by Prim's algorithm such that the set of edges
selected so far cannot be extended to form an MST for G. In other words, e
j
is the
first edge where Prim's algorithm “went wrong.” Let T be the “true” MST. Call v
p
(p < j) the vertex connected by edge e
j
, that is, e
j
= (v
p
; v
j
).
Because T is a tree, there exists some path in T connecting v
p
and v
j
. There
must be some edge e
0
in this path connecting vertices v
u
and v
w
, with u < j and
w j. Because e
j
is not part of T, adding edge e
j
to T forms a cycle. Edge e
0
must
be of lower cost than edge e
j
, because Prim's algorithm did not generate an MST.
This situation is illustrated in Figure 11.23. However, Prim's algorithm would have
selected the least-cost edge available. It would have selected e
0
, not e
j
. Thus, it is a
contradiction that Prim's algorithm would have selected the wrong edge, and thus,
Prim's algorithm must be correct.
2
Example11.3
For the graph of Figure 11.20, assume that we begin by
marking Vertex A. From A, the least-cost edge leads to Vertex C. Vertex C
and edge (A, C) are added to the MST. At this point, our candidate edges
connecting the MST (Vertices A and C) with the rest of the graph are (A, E),
(C, B), (C, D), and (C, F). From these choices, the least-cost edge from the
MST is (C, D). So we add Vertex D to the MST. For the next iteration, our
edge choices are (A, E), (C, B), (C, F), and (D, F). Because edges (C, F)
and (D, F) happen to have equal cost, it is an arbitrary decision as to which
gets selected. Say we pick (C, F). The next step marks Vertex E and adds
edge (F, E) to the MST. Following in this manner, Vertex B (through edge
(C, B)) is marked. At this point, the algorithm terminates.
