Boruvka算法|贪婪算法-9-yiteyi-C++库

我们已经讨论了以下关于最小生成树的主题。最小生成树问题的应用 Kruskal最小生成树算法 Prim最小生成树算法在这篇文章中，我们将讨论Boruvka的算法。与Prim和Kruskal的算法一样，Boruvka的算法也是贪婪算法。下面是完整的算法。

null

1) Input is a connected, weighted and un-directed graph.2) Initialize all vertices as individual components (or sets).3) Initialize MST 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 MST if not already added.  5) Return MST.

下面是上述算法背后的想法（想法与 Prim的MST算法 ). 生成树意味着所有顶点都必须连接。因此，两个不相交的顶点子集（上面讨论过）必须连接起来才能生成一棵生成树。它们必须与最小权边连接，使之成为最小生成树。让我们用下面的例子来理解算法。

Boruvka's algorithm Image 1

最初，MST是空的。每个顶点都是单个组件，如下图中以蓝色突出显示。

Boruvka's algorithm Image 2

对于每个组件，找到将其连接到其他组件的最便宜的边缘。

Component                Cheapest Edge that connects                          it to some other component  {0}                           0-1  {1}                           0-1  {2}                           2-8  {3}                           2-3  {4}                           3-4  {5}                           5-6  {6}                           6-7  {7}                           6-7  {8}                           2-8

最便宜的边缘用绿色突出显示。现在MST变成了{0-1,2-8,2-3,3-4,5-6,6-7}。

Boruvka's algorithm Image 3

在上述步骤之后，组件是{0,1}、{2,3,4,8}、{5,6,7}。组件被蓝色包围。

Boruvka's algorithm Image 4

我们再次重复这个步骤，即，对于每个组件，找到将其连接到其他组件的最便宜的边缘。

Component                Cheapest Edge that connects                          it to some other component  {0,1}                        1-2 (or 0-7)  {2,3,4,8}                    2-5  {5,6,7}                      2-5

最便宜的边缘用绿色突出显示。现在MST变成了{0-1,2-8,2-3,3-4,5-6,6-7,1-2,2-5}

Boruvka's algorithm Image 5

在这个阶段，只有一个组件{0，1，2，3，4，5，6，7，8}具有所有边。由于只剩下一个组件，我们停止并返回MST。 实施： 下面是上述算法的实现。输入图形表示为边和边的集合联合查找数据结构用于跟踪组件。

C/C++

python

                         # Boruvka's algorithm to find Minimum Spanning                       
                         # Tree of a given connected, undirected and weighted graph                       
           
                         from                                     collections                                     import                                     defaultdict                       
           
                         #Class to represent a graph                       
                         class                                     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                       
                                                 else                                     if                                     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                       
                                                 # components 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()                       
           
                         #This code is contributed by Neelam Yadav                       

输出：

Edge 0-3 included in MSTEdge 0-1 included in MSTEdge 2-3 included in MSTWeight of MST is 19

关于Boruvka算法的有趣事实： 1） Boruvka算法的时间复杂度为O（E logv），这与Kruskal和Prim算法相同。 2） Boruvka的算法被用作在线性时间O（E）下工作的更快随机算法 . 3） Boruwka算法是Boruuvka在1926年发现的最古老的最小生成树算法，比计算机还早。该算法作为一种构建高效电力网络的方法发布。 练习： 上面的代码假设输入图是连接的，如果给出一个断开连接的图，它就会失败。扩展上述算法，使其也适用于断开连接的图，并生成一个林。 参考资料： http://en.wikipedia.org/wiki/Bor%C5%AFvka%27s_algorithm 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章