如何找到最大生成树？ [英] How to find maximum spanning tree?

问题描述

请问Kruskal算法为它最小生成树工作的对立面？我的意思是，选择最大重量（边缘）的每一步？

任何其他的想法找到最大生成树？

解决方案

是的是的话，

来源：<一href="http://www.stats.ox.ac.uk/~konis/Rcourse/exercise1.pdf">http://www.stats.ox.ac.uk/~konis/Rcourse/exercise1.pdf

  

的一种方法，用于计算最大   重量跨越的G网树 -   由于采用Kruskal - 可以概括为   如下：

     

  
1. 排序G的边成重量递减顺序。令T   边集包括所述的   最大重量生成树。设置T =   ∅。
  
2. 添加第一个边缘至T。
  
3. 添加的下一个边缘至T当且仅当它不形成在T的周期。如果   没有剩余边退出，   报告G将被断开。
  
4. 如果T具有n-1个边（其中n是顶点G中的数量）停止和   输出T。否则，请转到步骤3。
  

Does the opposite of Kruskal's algorithm for minimum spanning tree work for it? I mean, choosing the max weight (edge) every step?

Any other idea to find maximum spanning tree?

解决方案

yes it does,

source: http://www.stats.ox.ac.uk/~konis/Rcourse/exercise1.pdf

One method for computing the maximum weight spanning tree of a network G – due to Kruskal – can be summarized as follows.

1. Sort the edges of G into decreasing order by weight. Let T be the set of edges comprising the maximum weight spanning tree. Set T = ∅.
2. Add the first edge to T.
3. Add the next edge to T if and only if it does not form a cycle in T. If there are no remaining edges exit and report G to be disconnected.
4. If T has n−1 edges (where n is the number of vertices in G) stop and output T . Otherwise go to step 3.

这篇关于如何找到最大生成树？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！