Kruskal 最小生成树算法的反面是否适用?我的意思是,每一步都选择最大重量(边缘)?
找到最大生成树的任何其他想法?
Kruskal 最小生成树算法的反面是否适用?我的意思是,每一步都选择最大重量(边缘)?
找到最大生成树的任何其他想法?
是的,它确实。
由于 Kruskal,一种计算网络 G 的最大权重生成树的方法可以总结如下。
- 将 G 的边按权重降序排序。令 T 为构成最大权重生成树的边集。设置 T = ∅。
- 将第一条边添加到 T。
- 将下一条边添加到 T 当且仅当它在 T 中不形成循环。如果没有剩余边退出并报告 G 断开连接。
- 如果 T 有 n-1 条边(其中 n 是 G 中的顶点数),则停止并输出 T。否则转到步骤 3。
资料来源:https ://web.archive.org/web/20141114045919/http://www.stats.ox.ac.uk/~konis/Rcourse/exercise1.pdf 。
来自Wolfram MathWorld 的最大生成树:
“最大生成树是具有最大权重的加权图的生成树。它可以通过否定每条边的权重并应用Kruskal 算法来计算(Pemmaraju 和 Skiena,2003 年,第 336 页)。”
如果你反转每条边的权重并最小化,你会得到最大的生成树吗?如果可行,您可以使用相同的算法。当然,零权重将是一个问题。
虽然这个线程太旧了,但我有另一种方法可以在图中找到最大生成树 (MST) G=(V,E)
我们可以应用某种 Prim 算法来寻找 MST。为此,我必须为最大加权边缘定义切割属性。
Cut 属性:假设在任何时候我们都有一个集合 S,其中包含 MST 中的顶点(现在假设它是通过某种方式计算的)。现在考虑集合 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/V 中的顶点 u' 和 S/V 中的 v' 使得 u' 是 S 中的最后一个顶点,之后我们进入 S/V 并且 v' 是 S/V 中路径上的第一个顶点从 u 到 v 循环。
删除边 e'=(u',v') 并且结果图仍然是连接的,但是 e 的权重大于 e' [因为 e 是此时从 S 到 S/V 的最大加权边] 所以这个导致 MST 的权重总和大于原始 MST。所以这是一个矛盾。这意味着边 e 必须在每个 MST 中。
查找 MST 的算法:
Start from S={s} //s 为起始顶点 而 S 不包含所有顶点 做 { 对于 S 中的每个顶点 s 从 S/V 添加一个顶点 v 使得边 e=(s,v) 的权重最大 } 结束时
实现:我们可以使用最大堆/优先级队列来实现,其中键是从 S 中的顶点到 S/V 中的顶点的边的最大权重,值是顶点本身。在 S 中添加一个顶点等于堆中的 Extract_Max,并且在每个 Extract_Max 处更改与刚刚添加的顶点相邻的顶点的键。
因此需要 m 个 Change_Key 操作和 n 个 Extract_Max 操作。
Extract_Min 和 Change_Key 都可以在 O(log n) 中实现。n 是顶点数。
所以这需要 O(m log n) 时间。m 是图中的边数。
让我提供一个改进算法:
因此,我们将获得最大生成树。
这棵树满足树外的任何边,如果添加将形成一个循环,并且外面的边 <= 循环中的任何边权重
事实上,这是生成树成为最大生成树的充分必要条件。
PF。
必要的:很明显这是必要的,或者我们可以交换边缘以生成具有更大边缘权重和的树。
充分:假设树T1满足这个条件,T2是最大生成树。
那么对于边 T1 ∪ T2,有 T1-only 边,T2-only 边,T1 ∩ T2 边,如果我们将 T1-only 边 (x1, xk) 添加到 T2,我们知道它会形成一个循环,我们声称,在这个循环中,必须存在一个仅 T2 的边,其边权重与 (x1, xk) 相同。然后我们可以交换这些边,将产生一棵树,它有一个与 T2 相同的边,并且具有相同的边权重之和,重复这样做,我们将得到 T2。所以T1也是最大生成树。
证明主张:
假设这不是真的,在循环中我们必须有一条只有 T2 的边,因为 T1 是一棵树。如果 T2-only 边没有一个等于 (x1, xk) 的值,则每条 T2-only 边与树 T1 形成一个循环,那么 T1 有一个循环导致矛盾。
该算法取自 UTD 教授 R. Chandrasekaran 的笔记。可以参考这里:单一商品多端流程
否定原始图的权重并在否定图上计算最小生成树将给出正确答案。原因如下:对于两个图中的相同生成树,一个图的加权和是另一个图的否定。所以否定图的最小生成树应该给出原始图的最大生成树。
仅颠倒排序顺序并在顶点切割中选择重边并不能保证最大生成森林(克鲁斯卡尔算法生成森林,而不是树)。如果所有边都具有负权重,则从 kruskal 反向获得的 Max Spanning Forest 仍然是负权重路径。然而,理想的答案是不连贯的顶点森林。即|V|的森林 单例树,或 |V| 总重量为 0 的组件(不是最不负的)。
以保留顺序更改权重(您可以通过取负权重值并添加一个大数字来实现此目的,其目的是确保非负数)然后在最小生成树上运行您的家庭基于 geedy 的算法。