implementing kruskal's algorithm utilizing threads

Question

I'm implementing Kruskal's algorithm and I'd like to utilize threads. However I am not sure I know enough about the algorithm to do this.

What I imagine is that I'd different parts of the graph would be solved for and connected at the end. Can anyone point me in the right direction? Thanks.

Answer 1

From Wikipedia

Research has focused on solving the minimum spanning tree problem in a highly parallelized manner. With a linear number of processors it is possible to solve the problem in O(logn) time. A 2003 paper "Fast Shared-Memory Algorithms for Computing the Minimum Spanning Forest of Sparse Graphs" by David A. Bader and Guojing Cong demonstrates a pragmatic algorithm that can compute MSTs 5 times faster on 8 processors than an optimized sequential algorithm.[9] Typically, parallel algorithms are based on Boruvka's algorithm—Prim's and especially Kruskal's algorithm do not scale as well to additional processors.

So, you might look into the algorithm mentioned in that paper, but Kruskal probably won't benefit from multiple threads.

Answer 2

Kruskal's algorithm for MST is hard to parallelize because it considers edges in a strictly specified order. You should take a look at Boruvka's algorithm which is easier to parallelize as it can work on each subtree of a partial MST independently.