对于最小生成树，Kruskal算法的相反算法在IT技术中是否有效？我是指每一步选择最大权值（边）。
有没有其他想法来找到最大生成树？
如何找到最大生成树？
66
- user467871
1
我认为任何卡在这个问题上的人都可以从Chow Liu算法中得到一些提示。 - Lerner Zhang
8个回答
80
是的，它可以。
一种计算网络G的最大权重生成树的方法（由Kruskal提出）可以总结如下： 1. 将G的边按权重降序排序。令T为包含最大权重生成树的边集。设置T = ∅。 2. 将第一条边添加到T中。 3. 仅当下一条边不在T中形成环时才将其添加到T中。如果没有剩余的边，则退出并报告G为不连通。 4. 如果T具有n-1条边（其中n是G中顶点的数量），则停止并输出T。否则，转到步骤3。
来源：https://web.archive.org/web/20141114045919/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。
来源：https://web.archive.org/web/20141114045919/http://www.stats.ox.ac.uk/~konis/Rcourse/exercise1.pdf。
- systemkern
3
9非常晚才参加派对，但是是的，它确实有用。 - Chris Watts
如果我们按照递增顺序对边进行排序，并且在图保持连通的情况下以相同的顺序不断删除边，这种方法是否可行？ - Stuxen
是的，虽然编写测试（= if条件）来检查图形是否仍然有效更加困难。
祝一切顺利，Rainer - systemkern
45
- Tony The Lion
3
所以，我想我的假设是正确的 :) - user467871
反转权重！我有Skienna的书，但我没有从记忆中提取出那个要点。（这本书在家里，所以我无法参考。）谢谢你提醒我。这会给我很好的动力去更仔细地阅读。 - duffymo
1如果唯一重要的是最小生成树中有哪些边，则对于Kruskal算法而言，边的顺序是相关的。当你取反边权重时，顺序与原始权重相反时，顺序是相同的。 - Palec
6
如果你将每条边的权重取反并进行最小化，那么你是否会得到最大生成树呢？如果可以，你可以使用相同的算法。当然，零权重会是一个问题。
- duffymo
2
3零权重会有什么问题？ - Rusty Rob
3如果你寻找的是整个图中最大权重的树（而不是访问所有顶点的最大权重生成树），那么零权重不会成为问题，但负数权重将会成为问题：这个问题是NP难问题。 - j_random_hacker
4
尽管这个线程太旧了，但我有另一种方法来查找图G=（V，E）中的最大生成树（MST）。
我们可以应用某种Prim算法来查找MST。为此，我必须定义最大加权边的割属性。
割性质：假设在任何时候，我们都有一个包含在MST中的顶点集S（暂时假设它已经被计算出来了）。现在考虑集合S/V（不在MST中的顶点）：
声明：从S到S/V的边中具有最大权重的边将始终存在于每个MST中。
证明：假设在我们将顶点添加到集合S的某一点时，从S到S/V的最大加权边是e =（u，v），其中u在S中，v在S/V中。现在考虑一个不包含e的MST。将边缘e添加到MST中。它将在原始MST中创建一个循环。遍历循环并找到S中的顶点u'和S/V中的顶点v'，使得u'是我们进入S/V之后的最后一个顶点，并且v'是从u到v的路径上的循环中的第一个S/V中的顶点。
删除边缘e' =（u'，v'），结果图仍然连接，但边缘e的权重大于e' [因为e是此时从S到S/V的最大加权边]，因此这导致了MST的权重总和大于原始MST。因此这是一个矛盾。这意味着边缘e必须存在于每个MST中。
查找MST的算法：
从S = {s}开始// s是起始顶点 while S不包含所有顶点 do { 对于S中的每个顶点s 添加来自S/V的顶点v，使得边缘e =（s，v）的权重最大 } end while 实现： 我们可以使用Max Heap / Priority Queue来实现，其中键是从S到S/V的边的最大权重，值是顶点本身。将顶点添加到S等于从堆中提取Max，并且在每次Extract_Max更改刚添加的顶点相邻顶点的键。
因此，它需要m Change_Key操作和n Extract_Max操作。
Extract_Min和Change_Key都可以在O（log n）中实现。n是顶点数。
因此，这需要O（m log n）时间。m是图中的边数。
我们可以应用某种Prim算法来查找MST。为此，我必须定义最大加权边的割属性。
割性质：假设在任何时候，我们都有一个包含在MST中的顶点集S（暂时假设它已经被计算出来了）。现在考虑集合S/V（不在MST中的顶点）：
声明：从S到S/V的边中具有最大权重的边将始终存在于每个MST中。
证明：假设在我们将顶点添加到集合S的某一点时，从S到S/V的最大加权边是e =（u，v），其中u在S中，v在S/V中。现在考虑一个不包含e的MST。将边缘e添加到MST中。它将在原始MST中创建一个循环。遍历循环并找到S中的顶点u'和S/V中的顶点v'，使得u'是我们进入S/V之后的最后一个顶点，并且v'是从u到v的路径上的循环中的第一个S/V中的顶点。
删除边缘e' =（u'，v'），结果图仍然连接，但边缘e的权重大于e' [因为e是此时从S到S/V的最大加权边]，因此这导致了MST的权重总和大于原始MST。因此这是一个矛盾。这意味着边缘e必须存在于每个MST中。
查找MST的算法：
从S = {s}开始// s是起始顶点 while S不包含所有顶点 do { 对于S中的每个顶点s 添加来自S/V的顶点v，使得边缘e =（s，v）的权重最大 } end while 实现： 我们可以使用Max Heap / Priority Queue来实现，其中键是从S到S/V的边的最大权重，值是顶点本身。将顶点添加到S等于从堆中提取Max，并且在每次Extract_Max更改刚添加的顶点相邻顶点的键。
因此，它需要m Change_Key操作和n Extract_Max操作。
Extract_Min和Change_Key都可以在O（log n）中实现。n是顶点数。
因此，这需要O（m log n）时间。m是图中的边数。
- Imran
2
让我提供一个改进算法：
该树满足任何添加在树外的边都会形成循环，并且树外边权重 <= 循环中任何边的权重。
实际上，这是生成树为最大生成树的必要和充分条件。
证明：
必要性：显然，这是必要的，否则我们可以交换边以使树具有更大的边权和。
充分性：假设树 T1 满足此条件，T2 是最大生成树。
那么对于边 T1 ∪ T2，存在 T1-only 边，T2-only 边，T1 ∩ T2 边。如果我们向 T2 添加 T1-only 边(x1, xk)，则我们知道它将形成一个循环，并且我们声明，在该循环中必须存在一个与 (x1, xk) 具有相同边权的 T2-only 边。然后我们可以交换这些边将产生一棵具有与 T2 更多公共边且具有相同边权和的树，重复此过程我们将得到 T2。因此 T1 也是最大生成树。
证明声明：
假设它不是真的，在循环中我们必须有一个 T2-only 边，因为 T1 是一棵树。如果没有 T2-only 边的值等于 (x1, xk) 的值，则每个 T2-only 边都与树 T1 形成一个循环，然后 T1 有一个循环会导致矛盾。
这个算法出自 UTD 教授 R. Chandrasekaran 的笔记。你可以在这里参考：Single Commodity Multi-terminal Flows。
- 首先构建任意树（使用 BFS 或 DFS）
- 然后选择一条不在树上的边，将其添加到树上，形成一个循环，删除循环中权重最小的边。
- 继续进行此操作，直到考虑完所有其他边
该树满足任何添加在树外的边都会形成循环，并且树外边权重 <= 循环中任何边的权重。
实际上，这是生成树为最大生成树的必要和充分条件。
证明：
必要性：显然，这是必要的，否则我们可以交换边以使树具有更大的边权和。
充分性：假设树 T1 满足此条件，T2 是最大生成树。
那么对于边 T1 ∪ T2，存在 T1-only 边，T2-only 边，T1 ∩ T2 边。如果我们向 T2 添加 T1-only 边(x1, xk)，则我们知道它将形成一个循环，并且我们声明，在该循环中必须存在一个与 (x1, xk) 具有相同边权的 T2-only 边。然后我们可以交换这些边将产生一棵具有与 T2 更多公共边且具有相同边权和的树，重复此过程我们将得到 T2。因此 T1 也是最大生成树。
证明声明：
假设它不是真的，在循环中我们必须有一个 T2-only 边，因为 T1 是一棵树。如果没有 T2-only 边的值等于 (x1, xk) 的值，则每个 T2-only 边都与树 T1 形成一个循环，然后 T1 有一个循环会导致矛盾。
这个算法出自 UTD 教授 R. Chandrasekaran 的笔记。你可以在这里参考：Single Commodity Multi-terminal Flows。
- XueYu
1
有趣的方法。您能否在答案中添加算法的复杂度？谢谢。 - Thariq Nugrohotomo
1
将原图的权重取反并在取反后的图上计算最小生成树，将会得到正确的答案。这是为什么呢：对于两个图中相同的生成树，一个图的权重和是另一个图的取反值。因此，在取反后的图上计算最小生成树应该会得到原图的最大生成树。
- Shen Yang
1
你能详细说明一下“NEGATE”这个词吗？ - dqureshiumar
1
仅仅颠倒排序顺序并选择一个顶点割中的重边并不能保证得到最大生成森林（Kruskal算法产生森林而非树）。如果所有的边权值均为负数，那么从Kruskal算法进行反转得到的最大生成森林仍然会是一条负权重路径。因此，理想答案是由不相连顶点构成的森林。即具有|V|个独立树或|V|个总权重为0的分量的森林（而不是最小的负数）。
- Sojourner
1
为什么反转排序顺序不正确？ - LetsGoBrandon
0
按照预留顺序更改权重（您可以通过取负权值并添加一个较大的数字来实现此目的，以确保非负），然后在最小生成树上运行您的贪心算法。
- Qinsheng Zhang
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接