首页
登录
从业资格
Prim算法和Kruscal算法都是无向连通网的最小生成树的算法,Prim算法从
Prim算法和Kruscal算法都是无向连通网的最小生成树的算法,Prim算法从
最全题库
2022-08-02
80
问题
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/2408407.html
本试题收录于:
中级 软件设计师题库软件水平考试初中高级分类
中级 软件设计师
软件水平考试初中高级
相关试题推荐
需求分析阶段生成的文档中,用来描述企业中各项业务流程的是()A.数据字典 B
传统编译器进行词法分析、语法分析、代码生成等步骤的处理时,前一阶段处理的输出是后
有两个N*N的矩阵A和B,想要在微机(PC机)上按矩阵乘法基本算法编程实现计
采用插入排序算法对n个整数排序,其基本思想是:在插入第i个整数时,前i-1个整数
在开发一个字处理软件时,首先快速发布了一个提供基本文件管理、编辑和文档生成功能的
对现有软件系统中一些数据处理的算法进行改进,以提高效率,从而更快地响应用户服务要
不同加密机制或算法的用途、强度是不相同的,一个软件或系统中的加密机制使用是否合理
在结构化分析模型中,( )描述了所有在目标系统中使用和生成的数据对象。A.数据
结构化开发方法中,()主要包含对数据结构和算法的设计。对算法设计时,其主要依据
结构化开发方法中,()主要包含对数据结构和算法的设计。对算法设计时,其主要依据
随机试题
[img]2016m3x/ct_eyyjsbz2014j_eyyjsbreadd_0360_20163[/img]It’snoteasytou
[originaltext]M:Ican’treachTom.There’sabusysignal.W:Thenhangupand
关于活字印刷的说法,正确的有( )。A.世界上最早的活字印刷术是我国宋代毕昇发
D
A. B. C. D.
在探究凸透镜的成像规律时,把蜡烛放在凸透镜前30cm处,光屏上可接收到倒立缩小清
基金公司投资交易流程包括()。 Ⅰ、形成投资策略 Ⅱ、构建投资组合 Ⅲ、
大批赴美志愿者汉语教师在美国校园和社区内担当着文化使者的角色,来自四川的高中教师
以下所列药物中,老年人对其药理作用敏感性增高的是A.利尿药 B.抗凝血药 C
下列哪项不是风湿性心脏瓣膜病主动脉瓣狭窄的血流动力学变化A.左心室收缩压高于主动
最新回复
(
0
)