首页
登录
从业资格
Prim算法和Kruscal算法都是无向连通网的最小生成树的算法,Prim算法从
Prim算法和Kruscal算法都是无向连通网的最小生成树的算法,Prim算法从
admin
2022-08-02
48
问题
Prim算法和Kruscal算法都是无向连通网的最小生成树的算法,Prim算法从一个顶点开始,每次从剩余的顶点中加入一个顶点,该顶点与当前的生成树中的顶点的连边权重最小,直到得到一颗最小生成树;Kruscal算法从权重最小的边开始,每次从不在当前的生成树顶点中选择权重最小的边加入,直到得到一颗最小生成树,这两个算法都采用了 ( ) 设计策略,且 (请作答此空) 。A. 若网较稠密,则Prim算法更好B. 两个算法得到的最小生成树是一样的C. Prim算法比Kruscal算法效率更高D. Kruscal算法比Prim算法效率更高
选项
A. 若网较稠密,则Prim算法更好
B. 两个算法得到的最小生成树是一样的
C. Prim算法比Kruscal算法效率更高
D. Kruscal算法比Prim算法效率更高
答案
A
解析
Prim算法从扩展顶点开始,每次总是"贪心的"选择与当前顶点集合中距离最短的顶点,而Kruscal 算法从扩展边开始,每次总是"贪心的"选择剩余的边中最小权重的边,因此两个算法都是基于贪心策略进行的。
Prim 算法的时间复杂度为O(n2),其中n 为图的顶点数,该算法的计算时间与图中的边数无关,因此该算法适合于求边稠密的图的最小生成树;Kruscal 算法的时间复杂度为O(mlgm) ,其中m 为图的边数,该算法的计算时间与图中的顶点数无关,因此该算法适合于求边稀疏的图的最小生成树。当图稠密时,用 Prim 算法效率更高。但若事先没有关于图的拓扑特征信息时,无法判断两者的优劣。由于一个图的最小生成树可能有多棵, 因此不能保证用这两种算法得到的是同一棵最小生成树。
转载请注明原文地址:https://tihaiku.com/congyezige/2425201.html
本试题收录于:
初级程序员题库软件水平考试初中高级分类
初级程序员
软件水平考试初中高级
相关试题推荐
依那普利降压的作用原理是A.抑制血管紧张素Ⅱ生成B.抑制血管紧张素与受体结合C.
呋塞米作为降压药的作用原理是A.抑制血管紧张素Ⅱ生成B.抑制血管紧张素与受体结合
妊娠早期,胎儿的红细胞生成主要来自()A.骨髓 B.肝 C.脾 D.
网络通信中广泛使用的DES加密算法属于()。A.对称加密 B.非对称加密
IEEE802.3的MAC协议采用的监听算法是()。A.非坚持型监听 B
在生成树协议(STP)IEEE802.1d中,默认的桥ID的优先级是多少(
以太网控制策略中有三种监听算法,其中一种是:“一旦介质空闲就发送数据,假如介质忙
以太网控制策略中有三种监听算法,其中一种是:“一旦介质空闲就发送数据,假如介质忙
下面安全算法中,属于加密算法的是(),属于报文摘要算法的是()。A.MD5和3D
一个计算机算法是对特定问题求解步骤的一种描述。()并不是一个算法必须具备的特
随机试题
Hardshipdidnotendwithfreedom.Therewere【C1】______regionalvariationi
Beingassertiveisbeingabletocommunicatewithotherpeopleclearly.Ify
Thisnewschoolprincipalwilltake______thenextweek.A、placeB、effectC、post
下列有关评估机构的权利和责任的表述中,正确的有( )。A、如果委托人不如实提供执
利用U形管做渗透作用实验(U形管中间用半透膜隔开)时,当管的两侧液面不再变化时,
共用题干 王先生为某单位员工,助理理财规划师通过分析王先生的财务状况,了解到王
产品生命周期是指产品从进入市场开始,直至被市场淘汰,企业不再生产为止的全过程。产
李某从自己承包的土地上出人不便,遂与张某书面约定在张某承包的土地上开辟一条道路供
可增强糖尿病患者口服磺酰脲类药降糖作用,引起严重低血糖的药物是A.多烯磷脂酰胆碱
某电厂有两台300MW机组,采用发电机变压器组向500kV系统送电。 根据现
最新回复
(
0
)