首页
登录
从业资格
Prim算法和Kruscal算法都是无向连通网的最小生成树的算法,Prim算法从
Prim算法和Kruscal算法都是无向连通网的最小生成树的算法,Prim算法从
资格题库
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),与图中边数无关,该算法适合于稠密图。Kruskal算法的时间复杂度只和边有关系,为O(elog2e),由于Kruskal算法只与边有关,因此适合求稀疏图的最小生成树。
转载请注明原文地址:https://tihaiku.com/congyezige/2407860.html
本试题收录于:
中级 软件设计师题库软件水平考试初中高级分类
中级 软件设计师
软件水平考试初中高级
相关试题推荐
对现有软件系统中一些数据处理的算法进行改进,以提高效率,从而更快地响应用户服务要
在结构化分析模型中,( )描述了所有在目标系统中使用和生成的数据对象。A.数据
加密和解密是明文和密文之间的可逆转换,( )不属于加密算法。A.RSA B.
加密和解密是明文和密文之间的可逆转换,()不属于加密算法。 A.RSA B
对一段信息生成消息摘要是防止信息在网络传输及存储过程中被篡改的基本手段,____
结构化开发方法中,()主要包含对数据结构和算法的设计。对算法设计时,其主要依据
结构化开发方法中,(请作答此空)主要包含对数据结构和算法的设计。对算法设计时,其
对n个数排序,平均情况下时间复杂度最低的算法是()排序算法。A.直接插入排序
采用折半查找算法有序表{7,15,18,21,27,36,42,48,51,5
采用折半查找算法有序表{7,15,18,21,27,36,42,4
随机试题
泰山的每个季节都有独特的魅力。春天,绿茵茵的山坡上,争奇斗艳的花朵到处可见。夏天,泰山的雷暴雨堪称奇观。秋天,枫树叶漫山遍野,蔚蓝色的河水穿流而行。冬天
Thefirstpermanentpicturewasmadebyusing_________[originaltext]TodayI
Time______,thecelebrationwillbeheldasscheduled.A、permitB、permittingC、p
确定会计核算工作空间范围的前提条件是()。A.会计主体 B.持续经营 C.会
Ante主张A.以缺牙部位决定基牙数目 B.以上都不对 C.以牙合力比值决定
在客户关系管理理念里,客户价值的预测通常采用下列()方式进行。A.客户消费量最
下列各项,不属亚急性再型肝炎并发症的是A.脑水肿 B.消化道出血 C.血糖增
(2019年真题)侦查机关在办理一起武装暴乱案时,办案人员王某发现犯罪嫌疑人系其
确定颌位关系包括A.定位平面记录 B.下颌后退记录 C.面下1/3高度记录
妊娠早期羊水的主要来源是A.母血清经胎膜进入羊膜腔的透析液 B.胎儿尿液 C
最新回复
(
0
)