Hi Comparing BoruvkaSollins algorithm with Prims algorithm F

Hi,

Comparing Boruvka/Sollins algorithm with Prims algorithm, For what values of |E| (in terms of |V |) does Boaruvka/Sollins algorithm asymptotically beat Prim’s algorithm without preprocessing?

Solution

Prims algorithm:

Boruvka’s algorithm is also a Greedy algorithm. Below is complete algorithm.

1) Input is a connected, weighted and directed graph.

2) Initialize all vertices.

3) Initialize minimal spanning tree as empty.

4) While there are more than one components, do following

   for each component.

      a) Find the closest weight edge that connects this

          component to any other component.

      b) Add this closest edge to minimal spanning tree if not already added.

5) Return minimal spanning tree.

Boruvka’s algorithm runs in O(ElogV) time.

Prims algorithm takes O(E+VlogV) or O(V+ElogV).

Thank you.