{"id":26387,"date":"2017-12-21T20:56:55","date_gmt":"2017-12-21T15:26:55","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26387"},"modified":"2017-12-21T20:56:55","modified_gmt":"2017-12-21T15:26:55","slug":"greedy-algorithms-set-9-boruvkas-algorithm","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/greedy-algorithms-set-9-boruvkas-algorithm\/","title":{"rendered":"Greedy Algorithms | Set 9 (Boruvka\u2019s algorithm)"},"content":{"rendered":"

In this post, Boruvka\u2019s algorithm is discussed. Like Prim\u2019s and Kruskal\u2019s, Boruvka\u2019s algorithm is also a Greedy algorithm. Below is complete algorithm.<\/p>\n

1) Input is a connected, weighted and directed graph.\r\n2) Initialize all vertices as individual components (or sets).\r\n3) Initialize MST as empty.\r\n4) While there are more than one components, do following\r\n   for each component.\r\n      a)  Find the closest weight edge that connects this \r\n          component to any other component.\r\n      b)  Add this closest edge to MST if not already added.  \r\n5) Return MST.\r\n<\/pre>\n
Below is the idea behind above algorithm (The idea is same as Prim\u2019s MST algorithm<\/a>).<\/p>\n
A spanning tree means all vertices must be connected. So the two disjoint subsets (discussed above) of vertices must be connected to make a Spanning Tree. And they must be connected with the minimum weight edge to make it a Minimum Spanning Tree.<\/em><\/p>\n[ad type=”banner”]\n
Let us understand the algorithm with below example.<\/p>\n
\"Boruvka\u2019s<\/p>\n
Initially MST is empty. Every vertex is singe component as highlighted in blue color in below diagram.<\/p>\n
\"Boruvka\u2019s<\/p>\n
For every component, find the cheapest edge that connects it to some other component.<\/p>\n
Component                Cheapest Edge that connects \r\n                         it to some other component<\/strong>\r\n  {0}                           0-1\r\n  {1}                           0-1\r\n  {2}                           2-8\r\n  {3}                           2-3\r\n  {4}                           3-4\r\n  {5}                           5-6\r\n  {6}                           6-7\r\n  {7}                           6-7\r\n  {8}                           2-8<\/pre>\n
The cheapest edges are highlighted with green color<\/p>\n
\"Boruvka\u2019s<\/p>\n
After above step, components are {{0,1}, {2,3,4,8}, {5,6,7}}. The components are encircled with blue color.\"Boruvka\u2019s<\/p>\n
We again repeat the step, i.e., for every component, find the cheapest edge that connects it to some other component.<\/p>\n[ad type=”banner”]\n
Component                Cheapest Edge that connects \r\n                         it to some other component<\/strong>\r\n  {0,1}                        1-2 (or 0-7)\r\n  {2,3,4,8}                    2-5\r\n  {5,6,7}                      2-5<\/pre>\n
The cheapest edges are highlighted with green color. Now MST becomes<\/p>\n
\"Boruvka\u2019s<\/p>\n
At this stage, there is only one component {0, 1, 2, 3, 4, 5, 6, 7, 8} which has all edges. Since there is only one component left, we stop and return MST.<\/p>\n
Implementation:<\/strong>
\nBelow is implementation of above algorithm. The input graph is represented as a collection of edges and union-find data structure<\/a> is used to keep track of components.<\/p>\n
python programming:<\/p>\n
 
 <\/div> 
# Boruvka's algorithm to find Minimum Spanning# Tree of a given connected, undirected and weighted graph from collections import defaultdict #Class to represent a graphclass Graph:     def __init__(self,vertices):        self.V= vertices #No. of vertices        self.graph = [] # default dictionary to store graph               # function to add an edge to graph    def addEdge(self,u,v,w):        self.graph.append([u,v,w])     # A utility function to find set of an element i    # (uses path compression technique)    def find(self, parent, i):        if parent[i] == i:            return i        return self.find(parent, parent[i])     # A function that does union of two sets of x and y    # (uses union by rank)    def union(self, parent, rank, x, y):        xroot = self.find(parent, x)        yroot = self.find(parent, y)         # Attach smaller rank tree under root of high rank tree        # (Union by Rank)        if rank[xroot] < rank[yroot]:            parent[xroot] = yroot        elif rank[xroot] > rank[yroot]:            parent[yroot] = xroot        #If ranks are same, then make one as root and increment        # its rank by one        else :            parent[yroot] = xroot            rank[xroot] += 1     # The main function to construct MST using Kruskal's algorithm    def boruvkaMST(self):        parent = []; rank = [];          # An array to store index of the cheapest edge of        # subset. It store [u,v,w] for each component        cheapest =[]         # Initially there are V different trees.        # Finally there will be one tree that will be MST        numTrees = self.V        MSTweight = 0         # Create V subsets with single elements        for node in range(self.V):            parent.append(node)            rank.append(0)            cheapest =[-1] * self.V             # Keep combining components (or sets) until all        # compnentes are not combined into single MST         while numTrees > 1:             # Traverse through all edges and update            # cheapest of every component            for i in range(len(self.graph)):                 # Find components (or sets) of two corners                # of current edge                u,v,w =  self.graph[i]                set1 = self.find(parent, u)                set2 = self.find(parent ,v)                 # If two corners of current edge belong to                # same set, ignore current edge. Else check if                 # current edge is closer to previous                # cheapest edges of set1 and set2                if set1 != set2:                                             if cheapest[set1] == -1 or cheapest[set1][2] > w :                        cheapest[set1] = [u,v,w]                      if cheapest[set2] == -1 or cheapest[set2][2] > w :                        cheapest[set2] = [u,v,w]             # Consider the above picked cheapest edges and add them            # to MST            for node in range(self.V):                 #Check if cheapest for current set exists                if cheapest[node] != -1:                    u,v,w = cheapest[node]                    set1 = self.find(parent, u)                    set2 = self.find(parent ,v)                     if set1 != set2 :                        MSTweight += w                        self.union(parent, rank, set1, set2)                        print ("Edge %d-%d with weight %d included in MST" % (u,v,w))                        numTrees = numTrees - 1                         #reset cheapest array            cheapest =[-1] * self.V                      print ("Weight of MST is %d" % MSTweight)                                 g = Graph(4)g.addEdge(0, 1, 10)g.addEdge(0, 2, 6)g.addEdge(0, 3, 5)g.addEdge(1, 3, 15)g.addEdge(2, 3, 4) g.boruvkaMST()<\/code><\/pre> <\/div>\n
Output:<\/p>\n
Edge 0-3 included in MST\r\nEdge 0-1 included in MST\r\nEdge 2-3 included in MST\r\nWeight of MST is 19<\/pre>\n
Interesting Facts about Boruvka\u2019s algorithm:<\/strong>
\n1) Time Complexity of Boruvka\u2019s algorithm is O(E log V) which is same as Kruskal\u2019s and Prim\u2019s algorithms.<\/p>\n
2) Boruvka\u2019s algorithm is used as a step in a faster randomized algorithm that works in linear time O(E)<\/a>.<\/p>\n
3) Boruvka\u2019s algorithm is the oldest minimum spanning tree algorithm was discovered by Boruuvka in 1926, long before computers even existed. The algorithm was published as a method of constructing an efficient electricity network.<\/p>\n[ad type=”banner”]\n","protected":false},"excerpt":{"rendered":"
Greedy Algorithms Boruvka\u2019s algorithm – Minimum Spanning Tree Like Prim\u2019s and Kruskal\u2019s, Boruvka\u2019s algorithm is also a Greedy algorithm.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,1,83618],"tags":[78515,83640,83639,83645,78514,78517,78516,83644,83641,78519,78520,78518,83643,83642,83638],"class_list":["post-26387","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-coding","category-greedy-algorithms","tag-boruvka-algorithm-example","tag-boruvka-algorithm-ppt","tag-boruvka-algorithm-proof-of-correctness","tag-boruvka-vs-prim-vs-kruskal","tag-boruvkas-algorithm-c-code","tag-boruvkas-algorithm-implementation","tag-boruvkas-algorithm-java","tag-boruvkas-algorithm-parallel","tag-boruvkas-algorithm-pdf","tag-boruvkas-algorithm-pseudocode-boruvka-algorithm-ppt","tag-boruvkas-algorithm-python","tag-sollins-algorithm","tag-sollins-algorithm-in-data-structure","tag-sollins-algorithm-in-ds","tag-what-is-sollins-algorithm"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26387","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=26387"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26387\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26387"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26387"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26387"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}