给定一个带权的无向连通图。w:E->{1,2,3,4,5,6,7} -意味着只有7个权重。我需要使用O(n+m)中的Prim算法和O( m*a(m,n))中的Kruskal算法找到一棵生成树。
我不知道如何做到这一点,真的需要一些指导,如何权重可以帮助我在这里。
发布于 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)。
发布于 2012-05-28 16:51:19
据我所知,回答家庭作业并不受欢迎,但希望这对其他人有用,而不仅仅是你;)
Prim:
Prim是一种寻找最小生成树(MST)的算法,就像Kruskal一样。将算法可视化的一种简单方法是在一张纸上绘制图形。然后,在选定的所有节点上创建一条可移动的线(剪切)。在下面的示例中,集合A将是cut中的节点。然后选择通过切割的最小边,即从线内的节点到线外的节点。始终选择权重最低的边。添加新节点后,移动剪切,使其包含新添加的节点。然后重复该操作,直到所有节点都在剪切范围内。
该算法的简短总结是:
Kruskal:
Kruskal和Prim很相似,除了你没有切割。所以你总是选择最小的边。
如果使用二进制堆,则搜索最小边的速度比使用邻接矩阵存储最小边的速度更快。
希望这能有所帮助!
https://stackoverflow.com/questions/10781236
复制相似问题