当前位置:首页>文章>prim算法图解(prim算法和kruskal算法的区别)

prim算法图解(prim算法和kruskal算法的区别)

昨天我们看了kruskal算法,今天我们换种算法来求。仍然是洛谷上的题目。 14856:线路规划 时间限制:1Sec内存限制:128MB 题目描述 有n个村庄之间需要架设通信线路,使得任意两个村庄之间均可通信。两个村庄a,b间可通信,当且仅当它们之间存在一条通信线路或者存在村庄c使得a,c和b,c间均可通信。给出村庄之间架设通信线路的代价,求出最小的总代价。 输入 第一行包含两个整数n,m,分别表...

昨天我们看了kruskal算法,今天我们换种算法来求。仍然是洛谷上的题目。

14856: 线路规划

时间限制: 1 Sec 内存限制: 128 MB

题目描述

有n 个村庄之间需要架设通信线路,使得任意两个村庄之间均可通信。两个村庄a, b 间可通信,当且仅当它们之间存在一条通信线路或者存在村庄c 使得a,c 和b,c 间均可通信。给出村庄之间架设通信线路的代价,求出最小的总代价。

输入

第一行包含两个整数n,m,分别表示村庄数量和可以架设通信线路的村庄对数。以下m 行,每行三个整数a,b,c,表示村庄a,b之间架设线路的代价为c(村庄从0 开始编号)。

输出

一个整数,最小总代价。

样例输入

3 30 1 11 2 12 0 3

样例输出

2

提示

对于50% 的数据,n<=100,m <=n^2

对于全部数据,1<=n<=10^5; n-1<=m<=10^5,所有代价均在[0, 10^6] 范围内,保证问题有解。

题目大意就是给n个点,m对长度,求一个最小生成树。

prim算法图解(prim算法和kruskal算法的区别)prim算法图解(prim算法和kruskal算法的区别)

这个过程和Dijstra非常类似,也可以用堆优化。大家现在自己独立思考一下。这个算法和Dijstra有什么相同点?还有什么不同点?可以把你的答案放到评论区内!!

Prim堆优化的算法复杂度为O(E+VlgV)

我们再综合看一下Prim和Kruscal两个算法。其实两种算法的复杂度级别是差不多的。Kruscal需要并查集知识的前置,但Prim不需要。两者的核心思想其实都是贪心,只不过贪心所用的策略和方式不同。很难说孰优孰劣,所以大家针对不同的题型或者针对自己的个人喜好自行选用就行。举报

给TA打赏
共{{data.count}}人
人已打赏
文章

小米5s参数配置(6寸以下的小屏手机推荐)

2022-5-4 9:21:55

文章

免费查看cad图纸什么软件(最好用的看图纸软件介绍)

2022-5-4 9:21:57

0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
购物车
优惠劵
今日签到
有新私信 私信列表
搜索