首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
Prim算法和Kruscal算法都是无向连通网的最小生成树的算法,Prim算法从一个顶点开始,每次从剩余的顶点中加入一个顶点,该顶点与当前的生成树中的顶点的连边权重最小,直到得到一颗最小生成树;Kruscal算法从权重最小的边开始,每次从不在当前的生成树顶
Prim算法和Kruscal算法都是无向连通网的最小生成树的算法,Prim算法从一个顶点开始,每次从剩余的顶点中加入一个顶点,该顶点与当前的生成树中的顶点的连边权重最小,直到得到一颗最小生成树;Kruscal算法从权重最小的边开始,每次从不在当前的生成树顶
admin
2019-07-12
12
问题
Prim算法和Kruscal算法都是无向连通网的最小生成树的算法,Prim算法从一个顶点开始,每次从剩余的顶点中加入一个顶点,该顶点与当前的生成树中的顶点的连边权重最小,直到得到一颗最小生成树;Kruscal算法从权重最小的边开始,每次从不在当前的生成树顶点中选择权重最小的边加入,直到得到一颗最小生成树,这两个算法都采用了_______设计策略,且_______。
(65)
选项
A、若网较稠密,则Prim算法更好
B、两个算法得到的最小生成树是一样的
C、Prim算法比Kruscal算法效率更高
D、Kruscal算法比Prim算法效率更高
答案
A
解析
Prim算法和Kruscal算法都是基于贪心算法的应用。Prim算法的时间复杂度为O(n
2
),与图中边数无关,该算法适合于稠密图。Kruskal算法的时间复杂度只和边有关系,为O(elog
2
e),由于Kruskal算法只与边有关,因此适合求稀疏图的最小生成树。
转载请注明原文地址:https://jikaoti.com/ti/6HG7FFFM
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
使用白盒测试方法时,确定测试用例应根据__________和指定的覆盖标准。(2010年上半年试题)
路由器命令“Router(config—subif)#encapsulationdotlq1”的作用是__________。(2011年上半年试题)
下图是一个软件项目的活动图,其中顶点表示项目里程碑,连接顶点的边表示包含的活动,边上的值表示完成活动所需要的时间,则关键路径长度为__________。(2011年下半年试题)
VLAN之间的通信通过(18)________________实现。
软件开发中的瀑布模型典型地刻画了软件生存周期的阶段划分,与其最相适应的软件开发方法是(9)。
[程序]#include<ioStream.h>template<classT>classArray;template<classT>classArrayBody{friend
阅读下列说明和数据流图,回答问题1至问题3。说明某图书管理系统的主要功能是图书管理和信息查询。对于初次借书的读者,系统自动生成读者号,并与读者基本信息(姓名、单位、地址等)一起写入读者文件。系统的图书管理功能分为四个方面:购入新书、读者借
请在下列选项中选择合适的答案,填入图3-1、图3-2的方框a和方框b。B的公钥,B的私钥,摘要算法,A的私钥,A的公钥,会话密钥按照图3-2中的方法发送邮件时,使用不同的密码体制加密消息和消息摘要,请用150字以内文字简要说明这样做的理由。
现欲实现一个图像浏览系统,要求该系统能够显示BMP、JPEG和GIF三种格式的文件,并且能够在Windows和Linux两种操作系统上运行。系统首先将BMP、JPEG和GIF三种格式的文件解析为像素矩阵,然后将像素矩阵显示在屏幕上。系统需具有较好的扩展性以
文法G=({E),{+,*,(,),a},P,E),其中P由下列产生式组成E->E+E|E*E|(E)|a。它生成由a,+,*,(,)组成的算术表达式,该文法在乔姆斯基分层中属于(16)型文法,其对应的自动机是(17),如产生句子a*a+a,它的派生树是(
随机试题
预防中枢神经系统白血病时,常用作鞘内注射的化疗药是
A.生理需要B.安全需要C.爱与被爱的需要D.尊重的需要E.自我实现的需要发挥自己的潜能,实现自已的理想与抱负的需要是
患者,男,50岁,失眠症数年。关于其治疗与护理措施正确的是()
按照病理分类,婴幼儿最常见的肺炎是
流动资产是指预计在一个正常营业周期中变现、出售或耗用的资产。()
教师:教室正确选项为()
为保证满负荷,必须有多高的出勤率?如果该厂段优化组合掉20人,又要保护90%的出勤率,必须提高多少效率?
在FastEthernet中,为了使物理层在实现100Mbps速率时所使用的传输介质和信号编码方式的变化不会影响MAC子层,100BASE-T标准定义了______。
Readthefollowingpassageandfillintheblankswithitscontents.WritethemonyourANSWERSHEET.Asperthetermsandc
A、Byteachingwritershowtoimitate.B、Byidentifyingwriter’sstrengthandweakness.C、Bydevelopingwriter’spotential.D、By
最新回复
(
0
)