首页 > 试题广场 >

与克鲁斯卡尔（Kruskal）相比，普里姆（Prim）算法更

[单选题]

与克鲁斯卡尔（Kruskal）相比，普里姆（Prim）算法更适于求哪种网的最小生成树（）。

风吹列子归

A 克鲁斯卡尔算法每次添加新的边时都需要对剩下的边进行排序，所以对于边稠密的网，普利姆算法更适合

发表于 2018-04-09 17:42:04 回复(0)

醉倒在柏油路上

Prim算法时间复杂度为o(v2) 不依赖于E 所以更适用于求解边稠密的图的最小生成树。而克鲁斯卡尔构造生成树的时间复杂度为o(ElogE)所以克鲁斯卡尔更适用于边稀疏而顶点较多的图。

发表于 2020-11-28 17:24:53 回复(0)

牛客882122502号

Prim算法：有两重for循环，时间复杂度为O(n^2)，n为顶点个数，与边数无关，特别适合用稠密图求最小生成树。

Kruskal算法：构造最小生成树的时间复杂度为O(e^2)，改进通过堆排序方式时间复杂度为O(elog2e)，e为图的边数，执行的时间仅与图中的边数有关，与顶点数无关，适用于稀疏图求最小生成树。

发表于 2021-04-05 22:35:46 回复(0)

Xechos

A，prim算法时间复杂度O（n2），适用于求边稠密图的最小生成树

kruskal算法时间复杂度O（e loge）

发表于 2020-12-09 14:34:57 回复(0)

牛客274233608号

我大E了，没闪

发表于 2020-11-22 18:07:33 回复(0)

天尊墨宇

选A

克鲁斯卡尔算法每次添加新的边时都需要对剩下的边进行排序，所以对于边稠密的网，普利姆算法更适合。

发表于 2020-07-06 12:58:58 回复(0)

DonMuv

那么克鲁斯卡尔算法适合于顶点稀疏的还是边稀疏的

发表于 2019-11-05 10:05:06 回复(0)

芒果没有he

发表于 2017-03-25 19:14:29 回复(0)

提交观点

问题信息

树

上传者：城市里的养猫者

难度：

8条回答 10收藏 4119浏览

扫一扫，把题目装进口袋