A Comparative Study Of Minimal Spanning Tree Algorithms

The minimal spanning tree is a structure used in solving certain types of combinatorial optimization problems. Popular application areas include network design such as roads, telephone, electrical and cable-laying. There are two popular algorithms for acquiring the minimum spanning tree of a graph; These are Kruskal’s algorithm and Prim’s algorithm. The goal of this study is to implement these algorithms and find out which of them is more efficient. To achieve this, we implement and evaluate the complexity of the algorithms. In this paper both methods have been implemented on the road network of the 36 states in Nigeria and results of the implementation are presented. However, since this work is taken from a research in progress, the computational complexity of the two algorithms will be carried out and reported in another paper in the future.