Question

Show that Boruvka's algorithm has O(lgV) iterations.

Answer 1

`Hey,

Note: Brother if you have any queries related the answer please do comment. I would be very happy to resolve all your queries.

Looking at the psudocode below

 Input: A graph G whose edges have distinct weights
 Initialize a forest F to be a set of one-vertex trees, one for each vertex of the graph.
 While F has more than one component:
   Find the connected components of F and label each vertex of G by its component
   Initialize the cheapest edge for each component to "None"
   For each edge uv of G:
     If u and v have different component labels:
       If uv is cheaper than the cheapest edge for the component of u:
         Set uv as the cheapest edge for the component of u
       If uv is cheaper than the cheapest edge for the component of v:
         Set uv as the cheapest edge for the component of v
   For each component whose cheapest edge is not "None":
     Add its cheapest edge to F
 Output: F is the minimum spanning forest of G.

Borůvka's algorithm can be shown to take O(log V) iterations of the outer loop until it terminates, and therefore to run in time O(E log V), where E is the number of edges, and V is the number of vertices in G. In planar graphs, and more generally in families of graphs closed under graph minor operations, it can be made to run in linear time, by removing all but the cheapest edge between each pair of components after each stage of the algorithm.

Kindly revert for any queries

Thanks.