首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >Prim和Kruskal的算法复杂度

问Prim和Kruskal的算法复杂度
EN

Stack Overflow用户
提问于 2012-05-28 16:01:15
回答 2查看 9.9K关注 0票数 0

给定一个带权的无向连通图。w:E->{1,2,3,4,5,6,7} -意味着只有7个权重。我需要使用O(n+m)中的Prim算法和O( m*a(m,n))中的Kruskal算法找到一棵生成树。

我不知道如何做到这一点,真的需要一些指导,如何权重可以帮助我在这里。

EN

回答 2

Stack Overflow用户

发布于 2012-05-28 16:53:08

可以更快地对边权重进行排序。

在Kruskal算法中,你不需要O(M lg M)排序,你只需要使用计数排序(或任何其他O(M)算法)。因此,排序的最终复杂度为O(M),联合查找阶段的复杂度为O(Ma(m))。总而言之是O(Ma(m))。

对于Prim算法的情况。你不需要使用堆,你需要7个列表/队列/数组/任何东西(具有恒定的插入和检索时间),每个权重一个。然后,当你在寻找最便宜的输出边时,你检查这些列表中的一个是否是非空的(从最便宜的那个开始),并使用该边。由于7是一个常数,因此整个算法的运行时间为O(M)。

票数 3
EN

Stack Overflow用户

发布于 2012-05-28 16:51:19

据我所知,回答家庭作业并不受欢迎,但希望这对其他人有用,而不仅仅是你;)

Prim:

Prim是一种寻找最小生成树(MST)的算法,就像Kruskal一样。将算法可视化的一种简单方法是在一张纸上绘制图形。然后,在选定的所有节点上创建一条可移动的线(剪切)。在下面的示例中,集合A将是cut中的节点。然后选择通过切割的最小边,即从线内的节点到线外的节点。始终选择权重最低的边。添加新节点后,移动剪切,使其包含新添加的节点。然后重复该操作,直到所有节点都在剪切范围内。

该算法的简短总结是:

  1. 创建一个集合A,它将包含所选的verticies。它最初将包含一个由您选择的随机起始节点。
  2. 创建另一个集合B。它最初将为空,并用于标记所有选定的边。
  3. 选择边E (u,v),即从节点u到节点v的边。边E必须是权重最小的边,其节点u在集合A中,并且v不在A中。(如果有几条边具有相等的权重,则可以随机选择任何边)
  4. 添加边(u,MST将包含A中的节点,B将描述它们是如何连接的。

Kruskal:

Kruskal和Prim很相似,除了你没有切割。所以你总是选择最小的边。

  1. 创建一个集合A,它最初是空的。它将用于存储选定的边。
  2. 从集合E中选择权重最小的边E,该边还不在A中。(u,v) = (v,u),因此您只能遍历这条边一次direction.
  3. Add E到A。
  4. 重复2和3,直到A和E相等,即直到您选择了所有边。

如果使用二进制堆,则搜索最小边的速度比使用邻接矩阵存储最小边的速度更快。

希望这能有所帮助!

票数 2
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/10781236

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档