-1

G(V,E)给定一个具有权重函数的无向连通图w:E->R，一条边e(u,v)属于 E。以线性运行时复杂度运行的算法可以确保是否存在包含边 e 的最小生成树？

4

2 回答 2

3

从u开始执行深度优先搜索，忽略任何权重等于给定边权重或更重的边。如果 DFS 在没有访问v的情况下完成，这意味着不存在给定边是最重边的循环，因此给定边包含在某个最小生成树中。

于 2013-01-30T19:05:56.283 回答
2

这是要求您实施Prim 的最小生成树两次。

  • 第一次正常运行算法。记下 mst 的重量。

  • 第二次，不是像 Prim 算法通常那样从一棵空树开始，而是从树上已经存在的节点 u 和 v 开始——这与拥有边 e(u,v) 相同。然后继续构建 mst。

  • 最后，如果第二个 mst 与第一个 mst 的权重相同，则边 e(u,v) 可以在 mst 中。如果没有，则有一个较轻的 mst。

顺便说一句，2*O(n) 仍然是 O(n)

于 2013-01-31T03:13:33.547 回答