Comparison of Prim and Kruskal’s Algorithm

Abstract

The goal of this research is to compare the performance of the common Prim and the Kruskal of the minimum spanning tree in building up super metric space We suggested using complexity analysis and experimental methods to evaluate these two methods After analysing daily sample data from the Shanghai and Shenzhen 300 indexes from the second half of 2005 to the second half of 2007 the results revealed that when the number of shares is less than 100 the Kruskal algorithm is relatively superior to the Prim algorithm in terms of space complexity however when the number of shares is greater than 100 the Prim algorithm is more superior in terms of time complexity A spanning tree is defined in the glossary as a connected graph with non-negative weights on its edges and the challenge is to identify a maz weight spanning tree Surprisingly the greedy algorithm yields an answer For the problem of finding a min weight spanning tree we propose greedy algorithms based on Prim and Kruskal respectively Graham and Hell provide a history of the issue which began with Czekanowski s work in 1909 The information presented here is based on Rosen