我的作业有以下问题：
给出一个 O(n+m) 算法来确定边 e 是否会成为图的 MST 的一部分
（我们可以在这项任务中获得其他人的帮助，所以这不是作弊。）
我认为我可以做一个 BFS 并找出这条边是否是两层之间的一条边，如果是的话，这条边是否是这些层中最小的。但是当这条边不是 BFS 树的树边时我能说什么呢？
问问题
9556 次
3 回答
9
作为提示，如果一条边不是包含它的任何循环中最重的边，则存在一些包含该边的 MST。要看到这一点，请考虑任何 MST。如果 MST 已经包含边缘，那就太好了！我们完成了。如果不是，则将边缘添加到 MST 中。这会在图中创建一个循环。现在，找到该循环中最重的边并将其从图中删除。现在一切都仍然是连接的（因为如果两个节点曾经通过穿过该边缘的路径连接，现在它们可以通过以另一种方式绕过循环来连接）。此外，由于删除边的成本不小于相关边的成本（因为边不是循环中最重的边），所以这棵树的成本不能大于前。由于我们以 MST 开始，因此我们必须以 MST 结束。
使用这个属性，看看你是否可以在线性时间内找到边缘是否是任何循环上最重的边缘。
于 2011-09-02T19:16:06.747 回答
7
我们将使用MST 循环属性来解决这个问题，它表示，“对于图中的任何循环 C，如果 C 的边 e 的权重大于 C 的所有其他边的权重，则该边不能属于MST。”
现在，运行以下O(E+V)算法来测试连接顶点 u 和 v 的边 E 是否会成为某个 MST 的一部分。
步骤1
从边 E 的端点之一（u 或 v）运行 dfs，只考虑那些权重小于 E 的边。
第2步
情况 1 如果在这个 dfs 的末尾，顶点 u 和 v 连接起来，那么边 E 不能是某个 MST 的一部分。这是因为在这种情况下，图中肯定存在一个循环，边 E 具有最大权重，它不能是 MST 的一部分（来自循环属性）。
情况 2 但如果在 dfs 结束时 u 和 v 保持断开连接，则边 E 必须是某个 MST 的一部分，因为在这种情况下，E 绝不是它所属的循环的最大权重边。
于 2014-03-24T17:40:34.137 回答
1
查找是否有任何路径比当前路径 (u,v) 更便宜，从而创建到 u 和 v 的循环。如果是，则 (u,v) 不在 mst 上。否则就是。这可以通过割属性和循环属性来证明。
于 2012-03-17T05:30:23.220 回答