Best Programming Master

In this article, we will have a look at another interesting algorithm related to Graph Theory – Boruvka’s Algorithm . We will also look at a problem with respect to this algorithm, discuss our approach and analyze the complexities. Boruvka’s Algorithm is mainly used to find or derive a Minimum Spanning Tree of an Edge-weighted Graph. Let us have a quick look at the concept of a Minimum Spanning Tree. A Minimum Spanning Tree or a MST is a subset of edges of a Weighted, Un-directed graph; such that it connects all the vertices together. The resultant subset of the graph must have no cycles or loops within it. Moreover, It should have minimum possible total weight of the edges connecting the tree. Note: The Minimum Spanning Tree should connect all its vertices. A disconnected graph is not a MST. Let us understand this with an example, consider this graph: The above shown graph is an Edge-Weighted, undirected graph with 6 vertices. The minimum Spanning tree of the above graph loo