Difference between Boruvka and Kruskal in finding MST

Question

I would like to know the difference between Boruvkas algorithm and Kruskals algorithm.

What they have in common:

• both find the minimum spanning tree (MST) in a undirected graph
• both add the shortest edge to the existing tree until the MST is found
• both look at the graph in it`s entirety, unlike e.g. Prims algorithm, which adds one node after another to the MST
• Both algorithmns are greedy

The only difference seems to be, that Boruvkas perspective is each individual node (from where it looks for the cheapest edge), instead of looking at the entire graph (like Kruskal does).

It therefore seems to be, that Boruvka should be relatively easy to do in parallel (unlike Kruskal). Is that true?

Dwarfism

Answer 1

In case of Kruskal's algorithm, first of all we want to sort all edges from the cheapest to the most expensive ones. Then in each step we remove min-weight edge and if it doesn't create a cycle in our graph (which initially consits of |V|-1 separate vertices), then we add it to MST. Otherwise we just remove it.

Boruvka's algorithm looks for nearest neighbour of each component (initially vertex). It keeps selecting cheapest edge from each component and adds it to our MST. When we have only one connected component, it's done.

Finding cheapest outgoing edge from each node/component can be done easily in parallel. Then we can just merge new, obtained components and repeat finding phase till we find MST. That's why this algorithm is a good example for parallelism (in case of finding MST).

Regarding parallel processing using Kruskal's algorithm, we need to keep and check edges in strict order, that's why it's hard to achieve explicit parallelism. It's rather sequential and we can't do much about this (even if we still may consider e.g. parallel sorting). Although there were few approaches to implement this method in parallel way, those papers can be found easily to check their results.

Mechling

Answer 2

Your description is accurate, but one detail can be clarified: Boruvka's algorithm's perspective is each connected component rather than each individual node.

Your intuition about parallelization is also right -- this paper has more details. Excerpt from the abstract:

In this paper we design and implement four parallel MST algorithms (three variations of Boruvka plus our new approach) for arbitrary sparse graphs that for the first time give speedup when compared with the best sequential algorithm.

Equate

Thank you very much for the answer. – Dwarfism

Answer 3

The important difference between Boruvka's algorithm and Kruskal's or Prim's is that with Boruvka's you don't need to presort the edges or maintain a priority queue.

Boruvka's still incurs the extra log N factor in the cost, but it does it by requiring O(log N) passes over the edges.

You can parallelize Boruvka's algorithm, but you can also parallelize sorting, so I don't know if Boruvka's has any real advantages over Kruskal's in practice.

Carmelocarmen