An alternative for the implementation of Kruskal's minimal spanning tree algorithm

AbstractAn application of the bucket sort in Kruskal's minimal spanning tree algorithm is proposed. The modified algorithm is very fast if the edge costs are from a distribution which is close to uniform. This is due to the fact that the sorting phase then takes for an m edge graph an O(m) average time. The O(m log m) worst case occurs when there is a strong peak in the distribution of the edge costs