TITLE:
Research and Improvement of Kruskal Algorithm
AUTHORS:
Haiming Li, Qiyang Xia, Yong Wang
KEYWORDS:
Minimum Spanning Tree, Classical Kruskal Algorithm, Two Branch Kruskal Algorithm, Time Complexity
JOURNAL NAME:
Journal of Computer and Communications,
Vol.5 No.12,
October
30,
2017
ABSTRACT: 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.