如何找到最大生成树？

Question

如何找到最大生成树？

51 algorithm greedy minimum-spanning-tree kruskals-algorithm

与最小生成树的Kruskal算法相反吗？我的意思是,每一步选择最大重量(边缘)？

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

Answer 1

sys*_*ern 61

是的,它确实,

来源:https://web.archive.org/web/20141114045919/http : //www.stats.ox.ac.uk/~konis/Rcourse/exercise1.pdf

用于计算网络G的最大权重生成树的一种方法 - 由于Kruskal - 可以总结如下.

将G的边缘按重量降序排列.令T为包括最大权重生成树的边集.设T =∅.

将第一条边添加到T.

当且仅当它没有在T中形成循环时,将下一条边添加到T.如果没有剩余边缘退出并报告G断开连接.

如果T具有n-1个边(其中n是G中的顶点数),则停止并输出T. 否则转到第3步.

@banarun聚会很晚,但是,确实如此. (8认同)

Answer 2

Ton*_*ion 38

从这个网站:

"最大生成树是具有最大权重的加权图形的生成树.可以通过否定每条边的权重并应用Kruskal算法(Pemmaraju和Skiena,2003,第336页)来计算."

Answer 3

duf*_*ymo 6

如果您在每个边缘上反转重量并最小化,您是否获得最大生成树？如果可行,您可以使用相同的算法.当然,零重量将是一个问题.

+1因为这基本上适用于所有算法. (3认同)
零权重不会有问题，但如果您正在寻找总体上最大权重的树（而不是最大权重 *spanning* 树，它被限制访问所有顶点），那么 *negative* 权重将是一个问题：这个问题是NP难的。 (3认同)
零权重将是一个问题吗？ (2认同)

归档时间：	14 年，10 月前
查看次数：	74994 次
最近记录：	6 年，2 月前