Minimal spanning tree algorithm in parallel

Question

I know some minimal spanning tree algorithms: Boruvka, Prim, and Kruskal. Which of them can be implemented in parallel?

Thanks!

Answer 1

Of these 3 algorithms, the Boruvka algorithm can be easily parallelized.

A quote from the description of the Boruvka algorithm on algoritmy.net :

A significant advantage of the Borůvka algorithm is that it can be easily parallelized, since the choice of the cheapest outgoing edge for each component is completely independent of the choice made by other components.