Java Reference
In-Depth Information
figure 24.7
Kruskal's algorithm
after each edge has
been considered. The
stages proceed left-
to-right, top-to-
bottom, as numbered.
V
0
V
1
V
0
V
1
1
1
V
2
V
3
V
4
V
2
V
3
V
4
1
V
5
V
6
1
V
5
V
6
2
2
2
V
0
V
1
V
0
V
1
1
1
2
V
2
V
3
V
4
V
2
V
3
V
4
1
1
3
4
V
5
V
6
V
5
V
6
2
2
V
0
V
1
V
0
V
1
1
1
3
2
2
2
2
V
2
V
3
V
4
V
2
V
3
V
4
1
1
5
6
V
5
V
6
V
5
V
6
2
2
V
0
V
1
V
0
V
1
4
1
1
2
2
2
2
V
2
V
3
V
4
V
2
V
3
V
4
4
1
1
V
5
V
6
7
V
5
V
6
8
Ordering the edges for testing is simple enough to do. We can sort them at a
cost of and then step through the ordered array of edges. Alternatively,
we can construct a priority queue of edges and repeatedly obtain edges by
calling
deleteMin
. Although the worst-case bound is unchanged, using a priority
queue is sometimes better because Kruskal's algorithm tends to test only a small
fraction of the edges on random graphs. Of course, in the worst case, all the edges
may have to be tried. For instance, if there were an extra vertex
v
8
and edge (
v
5
,
v
8
) of cost 100, all the edges would have to be examined. In this case, a quicksort
at the start would be faster. In effect, the choice between a priority queue and an
initial sort is a gamble on how many edges are likely to have to be examined.
More interesting is the issue of how we decide whether an edge (
u, v)
should be accepted or rejected. Clearly, adding the edge (
u, v)
causes a cycle
if (and only if)
u
and
v
are already connected in the current spanning
forest,
The edges can be
sorted, or a priority
queue can be used.
EE
log
E
Search WWH ::
Custom Search