Java Reference
In-Depth Information
Marked
Unmarked
Vertices v , i < j
Vertices v , i >= j
i
i
''correct'' edge
e'
v
v
u
u
v
v
p
j
e
j
Prim's edge
Figure11.23
Prim's MST algorithm proof. The left oval contains that portion of
the graph where Prim's MST and the “true” MST T agree. The right oval contains
the rest of the graph. The two portions of the graph are connected by (at least)
edges e
j
(selected by Prim's algorithm to be in the MST) and e
0
(the “correct”
edge to be placed in the MST). Note that the path from v
w
to v
j
cannot include
any marked vertex v
i
, i j, because to do so would form a cycle.
11.5.2
Kruskal's Algorithm
Our next MST algorithm is commonly referred to as Kruskal's algorithm. Kruskal's
algorithm is also a simple, greedy algorithm. First partition the set of vertices into
jVj equivalence classes (see Section 6.2), each consisting of one vertex. Then pro-
cess the edges in order of weight. An edge is added to the MST, and two equiva-
lence classes combined, if the edge connects two vertices in different equivalence
classes. This process is repeated until only one equivalence class remains.
Example11.4
Figure 11.24 shows the first three steps of Kruskal's Alg-
orithm for the graph of Figure 11.20. Edge (C, D) has the least cost, and
because C and D are currently in separate MSTs, they are combined. We
next select edge (E, F) to process, and combine these vertices into a single
MST. The third edge we process is (C, F), which causes the MST contain-
ing Vertices C and D to merge with MST containing Vertices E and F. The
next edge to process is (D, F). But because Vertices D and F are currently
in the same MST, this edge is rejected. The algorithm will continue on to
accept edges (B, C) and (A, C) into the MST.
The edges can be processed in order of weight by using a min-heap. This is
generally faster than sorting the edges first, because in practice we need only visit
a small fraction of the edges before completing the MST. This is an example of
finding only a few smallest elements in a list, as discussed in Section 7.6.
