首页
登录
从业资格
Prim算法和Kruscal算法都是无向连通网的最小生成树的算法,Prim算法从
Prim算法和Kruscal算法都是无向连通网的最小生成树的算法,Prim算法从
admin
2022-08-02
95
问题
Prim算法和Kruscal算法都是无向连通网的最小生成树的算法,Prim算法从一个顶点开始,每次从剩余的顶点中加入一个顶点,该顶点与当前的生成树中的顶点的连边权重最小,直到得到一颗最小生成树;Kruscal算法从权重最小的边开始,每次从不在当前的生成树顶点中选择权重最小的边加入,直到得到一颗最小生成树,这两个算法都采用了 (请作答此空) 设计策略,且 ( ) 。A.分治B.贪心C.动态规划D.回溯
选项
A.分治
B.贪心
C.动态规划
D.回溯
答案
B
解析
Prim算法从扩展顶点开始,每次总是"贪心的"选择与当前顶点集合中距离最短的顶点,而Kruscal 算法从扩展边开始,每次总是"贪心的"选择剩余的边中最小权重的边,因此两个算法都是基于贪心策略进行的。
Prim 算法的时间复杂度为O(n2),其中n 为图的顶点数,该算法的计算时间与图中的边数无关,因此该算法适合于求边稠密的图的最小生成树;Kruscal 算法的时间复杂度为O(mlgm) ,其中m 为图的边数,该算法的计算时间与图中的顶点数无关,因此该算法适合于求边稀疏的图的最小生成树。当图稠密时,用 Prim 算法效率更高。但若事先没有关于图的拓扑特征信息时,无法判断两者的优劣。由于一个图的最小生成树可能有多棵, 因此不能保证用这两种算法得到的是同一棵最小生成树。
转载请注明原文地址:https://tihaiku.com/congyezige/2425009.html
本试题收录于:
初级程序员题库软件水平考试初中高级分类
初级程序员
软件水平考试初中高级
相关试题推荐
呋塞米作为降压药的作用原理是A.抑制血管紧张素Ⅱ生成B.抑制血管紧张素与受体结合
Excel学生成绩表如下表所示, 若要计算表中每个学生计算机文化和英语课的
在以太网协议中,出现发送冲突时采用()算法。A.坚持监听 B.二进制指数后
Windows系统安装时生成的DocumentsandSettings、Wi
IEEE802.3的MAC协议采用的监听算法是()。A.非坚持型监听 B
OSPF是一种内部网关协议,这种协议的特点是()。A.采用距离矢量算法自动进
以太网控制策略中有三种监听算法,其中一种是:“一旦介质空闲就发送数据,假如介质忙
下面安全算法中,属于加密算法的是(),属于报文摘要算法的是()。A.MD5和3D
一个计算机算法是对特定问题求解步骤的一种描述。()并不是一个算法必须具备的特
以太网控制策略中有三种监听算法,其中一种是:“一旦介质空闲就发送数据,假如介质忙
随机试题
InternationalSummerExchangeProgram1.AimsoftheprogramTocreatearew
[originaltext]W:DoyouagreewithAlGorethatthere’sanurgentdriveforus
A.1/3 B.3 C.1 D.0
A.大 B.小 C.相等 D.无法判断
1999年我国宪法修正案明确规定:“依法治国,建设社会主义法治国家。”根据宪法的
下列选项中,属于西方抽象绘画代表人物的是()。A.马蒂斯 B.雷诺阿 C
下列除哪项外,均为肠道菌的主要抗原A.O抗原B.H抗原C.荚膜抗原D.芽孢抗原E
关于火灾警报和消防应急广播系统的联动控制设计,正确的要求是()。A.火灾自动报
乳尖牙过早拔除易造成A.恒尖牙异位萌出 B.恒侧切牙异位萌出 C.恒中切牙异
关于合并范围,下列说法中正确的有()。A.母公司是投资性主体,应将其全部子公司
最新回复
(
0
)