我的作业有以下问题：
给出O（n + m）算法以找出边e是否是图的MST的一部分
（我们被允许在这项任务中得到别人的帮助，所以这不是作弊。）
我认为我可以做一个BFS并找出这个边缘是否是两个层之间的边缘，如果是，那么这个边缘是否是这些边缘中最小的边缘。但是当这个边缘不是BFS树的树边缘时，我能说什么呢？
作为提示，如果边缘不是包含它的任何循环中最重的边缘，则有一些MST包含该边缘。要看到这一点，请考虑任何MST。如果MST已经包含边缘，太棒了！我们完成了。如果没有，则将边缘添加到MST中。这会在图表中创建一个循环。现在，找到该循环中最重的边缘并将其从图形中移除。一切现在仍然连接（因为如果两个节点过去通过一条穿过该边缘的路径连接，现在它们可以通过绕另一个循环来连接）。此外，由于边缘的成本被删除并不比任何边缘的成本小（因为边缘不是周期中最重的边缘），这棵树的成本不能大于之前。因为我们从MST开始，所以我们必须以MST结束。
使用此属性，查看是否可以在线性时间内查找边缘是否是任何周期中最重的边缘。
我们将使用MST cycle property来解决这个问题，它说：“对于图中的任何周期C，如果C的边e的权重大于C的所有其他边的权重，则该边不能属于MST。 “
现在，运行以下O(E+V)算法来测试连接顶点u和v的边E是否是某个MST的一部分。
步骤1
从边缘E的一个端点（u或v）运行dfs，只考虑那些权重小于E的边缘。
第2步
情况1如果在此dfs的末尾，顶点u和v连接，则边E不能是某些MST的一部分。这是因为在这种情况下，图中肯定存在一个周期，边E具有最大权重，并且它不能是MST的一部分（来自循环特性）。
情况2但是如果在dfs u和v的末尾保持断开连接，则边E必须是某些MST的一部分，因为在这种情况下，E绝不是它所属的循环的最大权重边。
找出是否有比当前路径更便宜的路径（u，v）为u和v创建一个循环。如果是，那么（u，v）不在mst上。否则就是。这可以通过cut属性和循环属性来证明。