设 G = (V, E) 为带权连通无向图，e 为 E 中的任意边。 展示一个线性时间算法来决定是否存在包含边 e 的最小生成树。
我设法找到了问题 1 的一个奇怪的“解决方案”，它似乎有效，但我认为它不是线性的:
他们建议使用 union find 并对每条边 (u,v) 进行 Union(u,v) 操作，使得 W(u,v) < W(e)。现在，假设 e = (x,y)。现在，如果 find(x) != find(y) 则 x 和 y 不相连，并且 W(e) 肯定是 Kruskal 算法检查的下一个权重，因此肯定存在包含边的 MST e.
另一方面，如果 find(x) = find(y) 那么如果我们运行 Kruskal 算法到这一点，x 和 y 肯定会连接，所以我们不能将边 e 添加到任何 MST(众所周知通过操纵具有相同权重的边的排序顺序 - Kruskal 算法可用于创建任何 MST)。
我不明白为什么这是线性的？由于联合，它不应该花费 O( |E| alpha(|V|) ) 吗？
也许还有另一种方法可以在线性时间内做到这一点？
提前致谢
最佳答案
如果我们采用 Kruskal 算法到“这个”点，标记到目前为止构建的连通分量，并将所有丢弃的边添加回来，每个连通分量仍将包含与之前相同的所有顶点(丢弃的边仅添加循环，而不是连接不同的组件)。因此，我们只需要检查e是否连接了两个不同的连接组件，这些组件由严格比e更亮的边组成。查找连接的组件是一项线性时间工作。
关于algorithm - 判断线性时间内是否存在包含给定边的 MST，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/15173922/