nod*_*ddy 9 algorithm minimum-spanning-tree
我的作业有以下问题:
给出O(n + m)算法以找出边e是否是图的MST的一部分
(我们被允许在这项任务中得到别人的帮助,所以这不是作弊.)
我认为我可以做一个BFS并找出这个边缘是否是两个层之间的边缘,如果是,那么这个边缘是否是这些边缘中最小的边缘.但是当这个边缘不是BFS树的树边缘时,我能说什么呢？
作为提示,如果边缘不是包含它的任何循环中最重的边缘,则有一些MST包含该边缘.要看到这一点,请考虑任何MST.如果MST已经包含边缘,太棒了!我们完成了.如果没有,则将边缘添加到MST中.这会在图表中创建一个循环.现在,找到该循环中最重的边缘并将其从图形中移除.一切现在仍然连接(因为如果两个节点过去通过一条穿过该边缘的路径连接,现在它们可以通过绕另一个循环来连接).此外,由于边缘的成本被删除并不比任何边缘的成本小(因为边缘不是周期中最重的边缘),这棵树的成本不能大于之前.因为我们从MST开始,所以我们必须以MST结束.
使用此属性,查看是否可以在线性时间内查找边缘是否是任何周期中最重的边缘.
我们将使用MST循环属性来解决这个问题,该属性表示"对于图中的任何循环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并不总是它所属的所有周期的最大权重边.