Prim算法和Kruscal算法都是无向连通网的最小生成树的算法,Prim算法从一个顶点开始,每次从剩余的顶点中加入一个顶点,该顶点与当前的生成树中的顶点的连边权重最小,直到得到一颗最小生成树;Kruscal算法从权重最小的边开始,每次从不在当前的生成树顶点中选择权重最小的边加入,直到得到一颗最小生成树,这两个算法都采用了 ( ) 设计策略,且 (请作答此空) 。

1151 次浏览
  • A、若网较稠密,则Prim算法更好
  • B、两个算法得到的最小生成树是一样的
  • C、Prim算法比Kruscal算法效率更高
  • D、Kruscal算法比Prim算法效率更高
"Prim算法从扩展顶点开始,每次总是""贪心的""选择与当前顶点集合中距离最短的顶点,而Kruscal 算法从扩展边开始,每次总是""贪心的""选择剩余的边中最小权重的边,因此两个算法都是基于贪心策略进行的。Prim 算法的时间复杂度为O(n2),其中n 为图的顶点数,该算法的计算时间与图中的边数无关,因此该算法适合于求边稠密的图的最小生成树;Kruscal 算法的时间复杂度为O(mlgm) ,其中m 为图的边数,该算法的计算时间与图中的顶点数无关,因此该算法适合于求边稀疏的图的最小生成树。当图稠密时,用 Prim 算法效率更高。但若事先没有关于图的拓扑特征信息时,无法判断两者的优劣。由于一个图的最小生成树可能有多棵, 因此不能保证用这两种算法得到的是同一棵最小生成树。"
挑战成功
2年前