首页
题库
面试
求职
学习
竞赛
More+
所有博客
搜索面经/职位/试题/公司
搜索
我要招人
去企业版
登录 / 注册
首页
>
试题广场
>
判断下列说法是否正确:相比于Kruskal算法,Prim算法
[单选题]
判断下列说法是否正确:相比于
Kruskal
算法,
Prim
算法更适合于求边稠密的无向网的最小代价生成树。()
正确
错误
添加笔记
邀请回答
收藏(189)
分享
4个回答
添加回答
8
推荐
白驹之过隙
选
A
。该题考察的是求最小生成树两种算法的使用场景。
Prim
算法从1个起点0条边出发,不断扩充顶点,直到包含所有顶点,适用于求边稠密的最小生成树。
Kruskal
算法从n个顶点n条边出发,不断扩充边,直到包括n-1条边为止,适用于求边稀疏的最小生成树。
编辑于 2019-10-25 14:28:14
回复(0)
7
天尊墨宇
选
A
。该题考察的是求最小生成树两种算法的使用场景。
Prim算法从1个起点0条边出发,不断扩充顶点,直到包含所有顶点,适用于求边稠密的最小生成树。
Kruskal算法从n个顶点n条边出发,不断扩充边,直到包括n-1条边为止,适用于求边稀疏的最小生成树。
发表于 2020-06-20 14:11:25
回复(0)
2
Cola_kkkk
选择A正确,在求最小代价生成树时,kruskal算法利用贪心的算法思想对每个边的权值排序,然后选取最小的边,再看两个节点是否连通,而prim直接在一个集合中选取一个点,然后选择边权值最小的。故在边稠密的无向图中,prim算法更为合适
发表于 2019-10-27 11:00:28
回复(0)
0
GoAshore
假设网中有n个节点和e条边,普利姆算法的时间复杂度是O(n^2),克鲁斯卡尔算法的时间复杂度是O(eloge),可以看出前者与网中的边数无关,而后者相反。因此,普利姆算法适用于边稠密的网络而克鲁斯卡尔算法适用于求解边稀疏的网。
发表于 2022-11-26 19:29:17
回复(0)
这道题你会答吗?花几分钟告诉大家答案吧!
提交观点
问题信息
图
上传者:
zsw3
难度:
4条回答
189收藏
4240浏览
热门推荐
相关试题
明明的随机数
数组
评论
(3704)
来自
华为研发工程师编程题
体育课测验(二)
广度优先搜索(BFS)
拓扑排序
dfs
评论
(2)
防火墙是怎么实现的?
计算机网络基础
评论
(1)
PMOS和NMOS的区别
元器件
评论
(1)
“乔布斯不做调查,张小龙不看数据。...
用户研究
评论
(1)
扫描二维码,关注牛客网
意见反馈
下载牛客APP,随时随地刷题