我的作业有以下问题:
(我们被允许从其他人那里获得帮助，所以这不是在作弊。)
我认为我可以做一个BFS，并确定该边缘是否为两层之间的边缘，如果是，则该边缘是否在这些层之间最小。但是，当该边缘不是BFS树的树边缘时，我能说什么呢？
最佳答案
作为提示，如果边缘不是包含该边缘的任何循环中最重的边缘，则存在一些包含该边缘的MST。要看到这一点，请考虑使用任何MST。如果MST已经包含边缘，那就太好了!大功告成!如果不是，则将边添加到MST中。这将在图形中创建一个循环。现在，找到该循环中最重的边并将其从图形中删除。现在一切仍然保持连接(因为如果两个节点以前是通过跨越该边缘的路径连接的，那么现在可以通过以另一种方式绕过循环来连接它们)。此外，由于删除边的成本不小于所讨论边的成本(因为该边不是循环中最重的边)，因此该树的成本不能大于该边的成本。前。由于我们从MST开始，因此我们必须以MST结尾。
使用此属性，查看是否可以找到该边沿是否为线性时间中任何周期上最重的边沿。
关于algorithm - 查找最小生成树是否在线性时间中包含边？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/7287899/