与克鲁斯卡尔最小生成树算法相反的算法是否适用?我的意思是,每一步选择最大权重(边缘)?
还有其他找到最大生成树的想法吗?
是的,它确实。
计算网络 G 的最大权生成树的一种方法 –
由于克鲁斯卡尔——可以总结如下。
- 按权重将 G 的边按降序排序。令 T 为构成最大权生成树的边集。设 T = ∅。
- 将第一条边添加到 T。
- 当且仅当它在 T 中不形成循环时,将下一条边添加到 T。如果
没有剩余边退出并报告G已断开。
- 如果 T 有 n−1 条边(其中 n 是 G 中的顶点数),则停止并
输出 T 。否则转至步骤 3。
Source: https://web.archive.org/web/20141114045919/http://www.stats.ox.ac.uk/~konis/Rcourse/exercise1.pdf https://web.archive.org/web/20141114045919/http://www.stats.ox.ac.uk/~konis/Rcourse/exercise1.pdf.
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)