Parallel union find algorithm

Question

I need to parallelize kruskal's algorithm, the serial version used the union find algorithm for detecting cycle in the undirected graph. Is there any way to parallelize this part of code?

Answer 1

Well, it can be parallelized to some extent. It is as follows:

Initially all the edges are sorted in the ascending order. There is a main thread which actually scans each edge from the beginning and decides whether adding the current edge forms the cycle. Our main aim in parallelizing the algorithm is to make these checks parallel.

This is where we use the worker threads. Each thread is given certain number of edges to examine, where in each thread checks if its edges form a cycle with the current representation after every iteration (iteration means the main thread adding a new edge). As the main thread keeps on adding the edges, some threads see that certain edges are already forming a cycle with the current representation.

Such edges are marked as discarded. When the main thread reaches such edges, it simply moves on to the next one without making any check on it.

Thus, we have actually made these checks parallel, which means the algorithm runs quickly increasing the efficiency.

In fact, there is a nice paper that uses the same idea described above.

EDIT:

If you are pretty much concerned about the running time of over-all algorithm, you can even use a parallel sorting algorithm initially as @jarod42 suggested.