首页
登录
从业资格
Prim算法和Kruscal算法都是无向连通网的最小生成树的算法,Prim算法从
Prim算法和Kruscal算法都是无向连通网的最小生成树的算法,Prim算法从
admin
2022-08-02
28
问题
Prim算法和Kruscal算法都是无向连通网的最小生成树的算法,Prim算法从一个顶点开始,每次从剩余的顶点中加入一个顶点,该顶点与当前的生成树中的顶点的连边权重最小,直到得到一颗最小生成树;Kruscal算法从权重最小的边开始,每次从不在当前的生成树顶点中选择权重最小的边加入,直到得到一颗最小生成树,这两个算法都采用了(请作答此空)设计策略,且( )。A.分治B.贪心C.动态规划D.回溯
选项
A.分治
B.贪心
C.动态规划
D.回溯
答案
B
解析
Prim算法和Kruscal算法都是基于贪心算法的应用。Prim算法的时间复杂度为O(n2),与图中边数无关,该算法适合于稠密图。Kruskal算法的时间复杂度只和边有关系,为O(elog2e),由于Kruskal算法只与边有关,因此适合求稀疏图的最小生成树。
转载请注明原文地址:https://tihaiku.com/congyezige/2407863.html
本试题收录于:
中级 软件设计师题库软件水平考试初中高级分类
中级 软件设计师
软件水平考试初中高级
相关试题推荐
对现有软件系统中一些数据处理的算法进行改进,以提高效率,从而更快地响应用户服务要
不同加密机制或算法的用途、强度是不相同的,一个软件或系统中的加密机制使用是否合理
在结构化分析模型中,( )描述了所有在目标系统中使用和生成的数据对象。A.数据
对一段信息生成消息摘要是防止信息在网络传输及存储过程中被篡改的基本手段,____
不同加密机制或算法的用途、强度是不相同的,一个软件或系统中的加密机制使用是否合理
结构化开发方法中,(请作答此空)主要包含对数据结构和算法的设计。对算法设计时,其
传统编译器进行词法分析、语法分析、代码生成等步骤的处理时,前一阶段处理的输出是后
下列算法中,不属于公开秘钥加密算法的是()? A.ECC B.DSA C
采用折半查找算法有序表{7,15,18,21,27,36,42,48,51,5
采用折半查找算法有序表{7,15,18,21,27,36,42,4
随机试题
我若为王,我的姓名就会改作:“万岁”,我的每一句话都成为:“圣旨”。我的意欲,我的贪念,乃至每一个幻想,都可竭尽全体臣民的力量去实现,即使是无法实现的。
______(他试图劝她打消离职的念头),butshesaidshewasresolvedtogobecauseshehadthough
Oneafternoonrecently,twounrelatedfriendscalledtotellmethat,well,
威尼斯面临的问题具有典型意义。一方面,为了解决市民的就业,增加城市的经济实力,必
停电拉闸操作应按照()的顺序依次进行。 A.断路器(开关)—电源侧隔离
尽管大家开始抵制珍稀动物的皮草产品,但仍有家具制造商将珍惜动物的皮毛用于家具饰品
现有按年收益率10%,每年付息一次的100元债券,期限5年。 根据上述材料,回
2×18年1月1日,甲公司开始推行一项奖励积分计划。根据该计划,客户在甲公司每消
单台发电机组容量为300MW及以上的火电厂的企业消防站,应设置不少于2辆消车,消
最新回复
(
0
)