MST:反向删除算法
MST:反向删除算法
提问于 2020-03-27 21:50:58
反向删除算法:从包含所有边的图开始。然后按权重的递减顺序重复通过边缘。对于每条边，检查删除该边是否会断开该图的连接；如果不会，则删除它。
如何证明此算法计算MST？
回答 1
Stack Overflow用户
发布于 2020-12-14 07:05:58
证明:首先，我们证明了该算法生成了一个生成树。这是因为图在开始时是连通的，当以非递增顺序删除边时，只删除了任何循环中最昂贵的边，这确实消除了循环，但不会断开图的连接，导致在结束时不包含任何循环的连通图。为了证明所获得的生成树是MST，请考虑算法删除的任何边。可以观察到，它必须位于某个循环上(否则删除它将断开图的连接)，并且它必须是其中最昂贵的一个(否则保留它将违反循环属性)。因此，“反向删除”算法生成一个MST。
在王晓春；王，夏利；威尔克斯，D。米切尔。一种基于最小生成树的分而治之的聚类方法。IEEE知识与数据工程学报，2009，21.7: 945-958。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/60887403
复制相关文章
相似问题
腾讯云开发者
