Prim算法和Kruscal算法都是无向连通网的最小生成树的算法，Prim算法从一个顶点开始，每次从剩余的顶点中加入一个顶点，该顶点与当前的生成树中的顶点的连边权重最小，直到得到一颗最小生成树；Kruscal算法从权重最小的边开始，每次从不在当前的生成树顶

admin2019-07-12 28

问题 Prim算法和Kruscal算法都是无向连通网的最小生成树的算法，Prim算法从一个顶点开始，每次从剩余的顶点中加入一个顶点，该顶点与当前的生成树中的顶点的连边权重最小，直到得到一颗最小生成树；Kruscal算法从权重最小的边开始，每次从不在当前的生成树顶点中选择权重最小的边加入，直到得到一颗最小生成树，这两个算法都采用了_______设计策略，且_______。
(65)

选项 A、若网较稠密，则Prim算法更好
B、两个算法得到的最小生成树是一样的
C、Prim算法比Kruscal算法效率更高
D、Kruscal算法比Prim算法效率更高

答案A

解析 Prim算法和Kruscal算法都是基于贪心算法的应用。Prim算法的时间复杂度为O(n²)，与图中边数无关，该算法适合于稠密图。Kruskal算法的时间复杂度只和边有关系，为O(elog₂e)，由于Kruskal算法只与边有关，因此适合求稀疏图的最小生成树。

转载请注明原文地址:https://www.kaotiyun.com/show/Q9CZ777K

本试题收录于：软件设计师上午基础知识考试题库软考中级分类

软件设计师上午基础知识考试

软考中级

相关试题推荐

随机试题

最新回复(0)

软件设计师上午基础知识考试

软考中级

OSPF协议使用(1)报文来保持与其邻居的连接。下面关于OSPF拓扑数据库的描述中，正确的是(2)。(2)

某主机本地连接属性如下图所示，下列说法中错误的是__________。(2012年下半年试题)

关于RIP，以下选项中错误的是(24)。

使用Telnet协议进行远程登陆时需要满足的条件不包括()。

假设系统中进程的三态模型如下图所示，图中的a、b和c的状态分别为__________。(2010年下半年试题)

在运行WindowsServer2008R2的DNS服务器上要实现IP地址到主机名的映射，应建立_____________记录。

SNMPv2提供了几种访问管理信息的方法，其中属于SNMPv2特有的是(50)。

数据流图4-1(住宅安全系统顶层图)中的A和B分别是什么?试说明逻辑数据流图(logicaldataflowdiagram)和物理数据流图(physicaldataflowdiagram)之间的主要差别。

阅读以下说明和Java代码，将应填入(n)处的字句写在答题纸的对应栏内。说明类Queue表示队列，类中的方法如下表所示。类Node表示队列中的元素；类EmptyQueueException给出了队列操作中的异常处理操作。Java代码

《中国药典》测定维生素B1原料药采用

患者，女，40岁。呕吐痰涎，伴头晕，胸痞，心悸，舌苔白，脉滑。治疗除取主穴外，还应加

选择市场分析公司可以采用公开招标、邀请招标和比选等方法。()适应于要求高、范围广、费用大的市场分析项目，时间比较长。

钢纤维混凝土属于()。

科目汇总表只在月末编制。()

对社会经济条件不同的纳税人区别课税，体现了税收的()。

债权人甲认为债务人乙怠于行使其债权给自己造成损害，欲提起代位权诉讼。下列各项债权中，不得提起代位权诉讼的有()。

脂肪的主要吸收部位是胃和小肠。()

“天河工程”论证会于2016年9月在青海省西宁市举行，“天河工程”用人工干预方式改变大气水汽分布，一旦成功，有望在青藏高原地区增加降水。完成下列问题。青藏高原的自然地理环境特征是()

Formostofhumanhistoryrichpeoplehadthemostleisure.Ontheotherhand,thepoorhavetypicallyworkedpersistently.Hans