包含边的最小生成树

Question

我想描述一个算法；

设 G 是加权的、未标出的图。给定一条边 'e'，是否存在包含这条 e 条边的 MST？

What I did: I built a graph:

G'=(V,E') | E={e'|e' -in E\{e} ,w(e')=< w(e)}

And now I just find if there is a path from u to v (u and v are the two sides of the edge e) using DFS or BFS

他们所做的是相同的，但有以下变化：

G'=(V,E') | E={e'|e' -in E ,w(e') < w(e)}`

我还是不明白算法怎么是真的？他们为什么不从 E 中排除 e ？

Answer 1

这个想法与 Kruskal 算法中的相同。

他们的正确性证明：
他们构建了一个图，其中包含边权重严格小于 w_e 的边。如果已经存在从 u 到 v 的路径，则 e 不能在 G 的任何 MST 中，因为 e 将是循环中的最大权重边。
此外，如果还没有从 u 到 v 的路径，那么我们可以添加 e（如 Kruskal 算法）并构建包含 e.[=26= 的 MST ]

你的情况：
您发现图的 MST 不包含 e 但具有权重 <= w_e 的边。如果已经存在从 u 到 v 的路径，则该路径可能包含权重等于 e 的边 e'。所以我们可以用 e 替换 e' 并得到一个 MST。因此，您的算法会检查 G.

的 all MST 中是否存在 e