The Application of Union-Find Sets in Kruskal Algorithm
Dazhi Pan, Zhibin Liu, Xianfeng Ding, Qin Zheng · 2009
It is the key of Krusal Algorithm to select edges and judge loop. Though realized path-compression in operation of searching tree of Union-Find Sets Data Structure, and optimized merging-operation which the shallower tree has been merged into the deeper tree, the operation of selecting edges and judging loop in Krusal Algorithm is optimized and the time complexity of algorithm is reduced. Compared with the common way, the programming operation time of the new way has been reduced to some 1/10.