Logo Data Structures and Algorithms with Object-Oriented Design Patterns in C++
next up previous contents index

Running Time Analysis

The KruskalsAlgorithm routine begins by creating an graph to hold the result spanning tree (lines 3-7). Since a spanning tree is a sparse graph the GraphAsLists class is used to represent it. Initially the graph contains tex2html_wrap_inline71781 vertices but no edges. The running time for lines 3-7 is tex2html_wrap_inline71805.

Next all of the edges in the input graph are inserted one-by-one into the priority queue (lines 9-18). Since there are tex2html_wrap_inline71793 edges, the worst-case running time for a single insertion is tex2html_wrap_inline72651. Therefore, the worst-case running time to initialize the priority queue is

displaymath72639

when adjacency lists are used, and

displaymath72640

when adjacency matrices are used to represent the input graph.

The main loop of the routine comprises lines 21-36. This loop is done at most tex2html_wrap_inline71793 times. In each iteration of the loop, one edge is removed from the priority queue (lines 23-25). In the worst-case this takes tex2html_wrap_inline72651 time.

Then, two partition find operations are done to determine the elements of the partition that contain the two end-points of the given edge (lines 26-29). Since the partition contains at most tex2html_wrap_inline71781 elements, the running time for the find operations is tex2html_wrap_inline73111. If the two elements of the partition are distinct, then an edge is added to the spanning tree and a join operation is done to unite the two elements of the partition (lines 30-34). The join operation also requires tex2html_wrap_inline73111 time in the worst-case. Therefore, the total running time for the main loop is tex2html_wrap_inline73115.

Thus, the worst-case running time for Kruskal's algorithm is

displaymath73091

when adjacency lists are used, and

displaymath73092

when adjacency matrices are used to represent the input graph.


next up previous contents index

Bruno Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.