Author(s)

Haiming Li, Qiyang Xia, Yong Wang

School of Computer and Information Engineering, Shanghai University of Electric Power, Shanghai, China.

It’s a very popular issue regarding the minimum cost spanning tree which is of great practical and economical significance to solve it in a concise and accelerated way. In this paper, the basic ideas of Kruskal algorithm were discussed and then presented a new improved algorithm—two branch Kruskal algorithm, which is improved to choose a middle value. Finally, because the time complexity is reduced, and the process is more convenient, it is concluded that the improved Kruskal algorithm is more effective in most cases compared with the Kruskal algorithm.

Minimum Spanning Tree, Classical Kruskal Algorithm, Two Branch Kruskal Algorithm, Time Complexity

Li, H. , Xia, Q. and Wang, Y. (2017) Research and Improvement of Kruskal Algorithm. Journal of Computer and Communications, 5, 63-69. doi: 10.4236/jcc.2017.512007.