Best parallel algorithm for detecting cycles in a undirect graph

Question

I want to detect cycles in an undirected graph such that I can find the minimum spanning tree (in particular I want to use Kruskal algorithm). Since I want to parallelize the code, I was wondering which algorithm is the best, Depth-first search of union-find algorithm? Thanks for any suggestions.

Answer 1

Of all three MST algorithms only Boruvka's MST algorithm is easily parallelizable whereas the kruskal and prims are sequential greedy algorithms hence there is minimum scope for parallel implementation of them.

Note: It is a research topic to achieve efficient parallel boruvka might find some papers