在一个只有k个不同边成本的图上，有没有一个算法可以找到一棵运行时间为O(n log k)的最小生成树？
在一个只有k个不同边成本的图上，有没有一个算法可以找到一棵运行时间为O(n log k)的最小生成树？
提问于 2011-02-18 00:54:09
这种算法在Skiena的算法设计一书中作为练习留给了读者，据推测它只是Prim算法的修改(In his wiki reference练习6-11)。有人能设计出这样的算法吗？
回答 2
Stack Overflow用户
回答已采纳
发布于 2011-02-18 06:56:26
具有简单优先级队列的素数是O(m+n lg n)，其中m是边的数量，n是顶点的数量。如果您存储具有相同优先级的条目(例如，使用链表)，则会自动得到O(m+n lg k)。
AFAIK，这种情况下的最新技术是O(m)，Fredman and Willard。
Stack Overflow用户
发布于 2011-02-18 22:11:34
是的，问题应该是O(m +n)。显然，Omega(m)是一个下界，因为如果不检查所有边，我们甚至找不到最低权重的边。
对于记录，约定是n表示顶点的数量，m表示边的数量。
喜欢我的书:-)
史蒂文·斯凯纳
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/5035309
复制相关文章
相似问题
腾讯云开发者
