algorithm - 在线性时间内查找最小生成树是否包含边？

Question

我的作业有以下问题:

Give an O(n+m) algorithm to find that whether an edge e would be a part of the MST of a graph

(我们可以在这个作业上得到其他人的帮助，所以这不是作弊。)

我认为我可以做一个 BFS 并找出这条边是否是两层之间的一条边，如果是的话，这条边是否是这些层中的最小边。但是当这条边不是 BFS 树的树边时我能说什么呢？

Answer 1

作为提示，如果一条边不是包含它的任何循环中最重的边，则存在一些包含该边的 MST。要看到这一点，请考虑任何 MST。如果 MST 已经包含边缘，那就太好了!我们完成了。如果不是，则将边缘添加到 MST 中。这会在图中创建一个循环。现在，找到该循环中最重的边并将其从图中删除。现在一切都仍然连接(因为如果过去两个节点通过一条穿过该边缘的路径连接，现在它们可以通过以另一种方式绕过循环来连接)。此外，由于删除边的成本并不比所讨论的边的成本小(因为边不是循环中最重的边)，所以这棵树的成本不能大于前。由于我们以 MST 开始，因此我们必须以 MST 结束。

利用这个性质，看看你是否能在线性时间内找到这条边是否是任何循环中最重的边。