我正在研究一种算法来检查给定的边缘是否包含在所有可能的 mst 之一中。
对于这个问题，我们正在考虑非不同的值，并且我们的边 e 连接顶点 A 和 B。
到目前为止，我有： 如果一条从 A 到 B 的路径由权重小于或等于我们边 e 的权重的边组成——我们可以说边 e 不是任何 MST 的一部分。
我在这里遗漏了什么/关于更好算法的想法吗？
编辑：
对涉及循环属性的解决方案有何想法--因此，我们考虑所有边的权重小于我们正在考虑的边。如果我们可以用这些边创建一条从 A->B 的路径，我们可以说它不是任何 MST 的一部分？
我们将使用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 始终不是它所属的所有循环中的最大权重边。
我会写下我对这个问题的看法。
循环属性在这里非常重要：任何循环中的最大边不能在最小生成树中。
为了证明循环属性，假设有一个最小生成树 T 包含边 e，它是循环中最大的成本边。然后我们可以删除树T中的边e，我们得到两个集合S和T。那么这个循环必须包含连接集合S和T的除e之外的其他边。那么从cut性质来看，边e不能是在最小生成树中。
一旦我们有了循环属性，我们就继续断言某个边 e 是否在最小生成树中：
当且仅当存在时，边 e(v,w) 不属于任何最小生成树从 v 和 w 开始的一条路径，其中这条路径上的每条边都小于 e。
使用上述声明，算法如下：
删除所有大于 e 的边，现在我们有图 G'。运行 DFS 以检查 v 和 w 是否在 G' 中连接。如果 v 和 w 仍然连接，则边 e 不属于任何最小生成树。如果 v 和 w 没有连接，则边 e 在某个最小生成树中。
为了检查一条边是否应该在 MST 中，您应该从检查将这条边添加到图中是否创建循环开始，我们都知道 MST 不能有任何循环。
如果是这样，那么只需找出至少两条路线中哪条路线的权重较小。如果你的边 e 的权重最小，那么它应该在 MST 中，否则它只是一个可以形成循环的边加上不是包含在图中的最佳边。
如果没有，它必须在 MST 中，除非以后有任何优势发挥作用并击败现有优势。
通过这样做，您可以实现 O(n) 时间检查边缘是否在 MST 中。
假设 AB 是您的图，而 e 是唯一的边。然后 e 是 MST 的一部分，但是有一条路径 AB 可以满足您的条件。
即使您要求 e 不是这样一条路径的一部分，它也是错误的。只需取一个在 A 和 B 之间具有相同权重的两条边 e1 和 e2 的图。
您还应该考虑一个图 ABC，它带有来自 AC 的附加边，其中所有边的权重为 1。无论您删除哪条边，您都可以获得最小生成树。因此，任何边都可以是 MST 的一部分。