我在面试时，面试官问了我一个问题：
我们有一个图g（v，e），我们可以使用prim或kruskal算法找到mst。但是，这些算法没有考虑到G中有“非常少”的边。我们如何利用这些信息来提高查找MST的时间复杂度？我们能在线性时间内找到MST吗？
我唯一记得的是kruskal的算法在稀疏图中更快，而prim的算法在真正稠密图中更快。但我无法回答他如何利用关于边数的先验知识在线性时间内生成MST。
如有任何见解或解决方案，将不胜感激。
最佳答案
Kruskal的算法在对边缘进行排序之后是非常线性的如果使用一个联合查找结构，如disjoint set forest，处理单个边的复杂性将是LG*（n）的顺序，其中n是顶点的数目，这个函数增长得很慢，因此这种情况可以被认为是常数。但是问题是，要对边进行排序，仍然需要O(m * log(m))。其中m是边的数目。
Prim的算法无法利用边缘很少的事实。
可以使用的一种方法类似于“反向”MST方法，从所有边开始，删除最长的边，直到图形断开连接一直这样直到只剩下n - 1边仍然需要注意的是，只有当要删除的边的数目足够少，以至于k时，这将比kruskal更好。
关于algorithm - 在线性时间内从具有“很少”边缘的图形构建MST，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/41851206/