Experimental study of performance of minimum spanning tree algorithms

Throughout the study of various theories of algorithms much work has been done in the area of traversal and solving optimization problems on graphs. Some of this work includes studies of finding the Minimal-Cost Spanning Trees (MST) in directed and undirected connected graphs. Several algorithms have been developed for such task. These algorithms tend to differ in performance based on various factors, such as graph density, size of problem spaces, range of weights that can be assigned to the edges of the graphs, edge weight distributions, etc. The data structures used by an algorithm can have a significant impact on algorithm\u27s performance, for each of the aforementioned factors. This thesis presents the results of the experimental study of the impact the data structures have on performances of Kruskal\u27s and Prim\u27s algorithms for finding Minimum-Cost Spanning Trees in connected undirected graphs. The goal of this study is to compare performance of the practical implementations of Kruskal\u27s and Prim\u27s algorithms to their theoretical counterparts, as well as to measure and compare the differences in performances for various implementations of one algorithm, with respect to different implementation of the essential data structures. Performances of different algorithms are studied with respect to each-other for several variations of the types of data. As a result, a table depicting a schedule for use of the various implementations of either of the algorithms, as related to the type of graph used, is presented. The algorithms are implemented and executed on a single Sun UltraSparc workstation, in order to eliminate the discrepancies, which may result from the differences in the processor speeds and variable CPU loads on multiple test machines. The following implementations are studied: Kruskal\u27s Algorithm with heapsort, and disjoint-sets using union-by-rank and path-compression heuristic Kruskal\u27s Algorithm with counting sort and disjoint-sets using union-by-rank and path-compression heuristic Prim\u27s Algorithm with brute force implementation of priority queues Prim\u27s Algorithm with priority queue implemented using a proper implementation of binary heap with bubble-up performed each time a decrease-key operation is performed for a vertex Prim\u27s Algorithm with priority queue implemented using a lazy implementation of binary heap with bubble-up performed after all decrease-key operations are performed for a vertex Prim\u27s Algorithm with priority queue implemented using a binomial heap Prim\u27s Algorithm with priority queue implemented using a Fibonacci heap Upon the conclusion of the experiment, the best results were obtained from the implementation of Prim\u27s algorithm using the lazy heap implementation of a priority queue. For sparse graphs, Kruskal\u27s algorithm with counting sort performed very well, while for higher density graphs, Prim\u27s algorithm with binomial heap performed very well