利用线性时间中“极少数”边的图建立MST
利用线性时间中“极少数”边的图建立MST
提问于 2017-01-25 12:04:39
我参加了一个面试，面试官问了我一个问题：
我们有一个图G(V，E)，我们可以用prim或kruskal算法找到MST。但是这些算法并没有考虑到G中有“很少”的边，我们如何利用这些信息来提高寻找MST的时间复杂度？我们能在线性时间内找到MST吗？
我唯一记得的是，Kruskal的算法在稀疏图中更快，而Prim的算法在真正密集的图中更快。但我无法回答他如何利用关于边数的先验知识在线性时间内生成MST。
如有任何见解或解决方案，将不胜感激。
回答 2
Stack Overflow用户
回答已采纳
发布于 2017-01-25 12:16:24
Kruskal的算法在对边缘进行排序后几乎是线性的。如果使用象不相交集林这样的并查找结构，处理单个边的复杂度将是lg*(n)，其中n是顶点数，这个函数增长得非常慢，在这种情况下可以认为是常数。然而，问题在于，要对边缘进行排序，仍然需要一个O(m * log(m))。其中m是边的数目。
Prim的算法将无法利用边缘非常少的事实。
您可以使用的一种方法是类似于“反向”MST方法，从所有边缘开始，并删除最长的边缘，直到图形断开为止。您一直这样做，直到只剩下n - 1边。仍然要注意的是，这将比Kruskal更好，只有当删除k的边数足够少时，才能使k * n < m * log(m)。
Stack Overflow用户
发布于 2021-08-27 13:24:43
让我们说，x-E=x-V +c，c是一个小常数。您可以在图形上运行DFS，每次检测到一个圆时，都可以删除最大的边缘。你必须做c +1次。理论上，O(c+1 *x~+E_x)= O(E)线性时间。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/41851206
复制相关文章
相似问题
腾讯云开发者
