我的作业有以下问题:
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 树的树边时我能说什么呢?
最佳答案
作为提示,如果一条边不是包含它的任何循环中最重的边,则存在一些包含该边的 MST。要看到这一点,请考虑任何 MST。如果 MST 已经包含边缘,那就太好了!我们完成了。如果不是,则将边缘添加到 MST 中。这会在图中创建一个循环。现在,找到该循环中最重的边并将其从图中删除。现在一切都仍然连接(因为如果过去两个节点通过一条穿过该边缘的路径连接,现在它们可以通过以另一种方式绕过循环来连接)。此外,由于删除边的成本并不比所讨论的边的成本小(因为边不是循环中最重的边),所以这棵树的成本不能大于前。由于我们以 MST 开始,因此我们必须以 MST 结束。
利用这个性质,看看你是否能在线性时间内找到这条边是否是任何循环中最重的边。
关于algorithm - 在线性时间内查找最小生成树是否包含边?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7287899/