Research and Improvement of Kruskal Algorithm

• 作者: Haiming Li Qiyang Xia Yong Wang
• 来源期刊: 电脑和通信(英文)
• 学科: 医学
• 关键词: Minimum SPANNING TREE CLASSICAL Kruskal ALGORITHM Two Branch Kruskal ALGORITHM Time COMPLEXITY
• 年，卷（期）: 2017,（12）
• 页码范围: 63-69
• 页数: 7页
• 分类号: R73

摘要

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.