Implementation of the kruskal algorithm using threads

Question

I am implementing the Kruskal algorithm and I would like to use streams. However, I'm not sure I know enough about this algorithm.

I think that I would decide that different parts of the graph will be resolved and connected at the end. Can someone point me in the right direction? Thanks.

Answer 1

From Wikipedia

The study focused on solving the problem of a minimum spanning tree with a high degree of parallelization. With a linear number of processors, you can solve the problem in O (logn). The 2003 article, “Fast Shared Memory Algorithms for Computing the Minimal Formwork Forest of Rare Graphics,” by David A. Bader and Guojing Kong, demonstrates a pragmatic algorithm that can calculate MSTs 5 times faster on 8 processors than an optimized sequential algorithm. [9] As a rule, parallel algorithms based on the Boruwka – Prim algorithm and especially the Kruskal algorithm do not scale processors as well.

So, you can take a look at the algorithm mentioned in this article, but Kruskal probably won't benefit from multiple threads.

Answer 2

The Kruskal algorithm for MST is difficult to parallelize as it considers edges in a strictly defined order. You should take a look at the Boruvka algorithm , which is easier to parallelize, since it can work independently of each subtree of a partial MST.