Java Reference
In-Depth Information
Initial
A
B
C
D
E
F
C
Step 1
A
B
E
F
1
Process edge (C, D)
D
C
F
Step 2
A
B
E
1
1
Process edge (E, F)
D
C
Step 3
A
B
1
2
Process edge (C, F)
D
F
E
1
Figure11.24
Illustration of the first three steps of Kruskal's MST algorithm as
applied to the graph of Figure 11.20.
The only tricky part to this algorithm is determining if two vertices belong to
the same equivalence class. Fortunately, the ideal algorithm is available for the
purpose — the UNION/FIND algorithm based on the parent pointer representation
for trees described in Section 6.2. Figure 11.25 shows an implementation for the
algorithm. Class
KruskalElem
is used to store the edges on the min-heap.
Kruskal's algorithm is dominated by the time required to process the edges.
The
differ
and
UNION
functions are nearly constant in time if path compression
and weighted union is used. Thus, the total cost of the algorithm is (jEjlogjEj)
in the worst case, when nearly all edges must be processed before all the edges of
the spanning tree are found and the algorithm can stop. More often the edges of the
spanning tree are the shorter ones,and only about jVj edges must be processed. If
so, the cost is often close to (jVjlogjEj) in the average case.
