最小生成树之prim算法和kruskal算法

浅浅的花香味﹌ 2022-05-27 10:49 222阅读 0赞

在日常生活中解决问题经常需要考虑最优的问题，而最小生成树就是其中的一种。看了很多博客，先总结如下，只需要您20分钟的时间，就能完全理解。

比如：有四个村庄要修四条路，让村子能两两联系起来，这时就有最优的问题，怎样修才是做好的，如下图：第一个是网全图，后三个图的修路方案都可以

![779158-20160830164224746-1316460800.png][]

1.树的定义：有n个顶点和n-1条边，没有回路的称为树

生成树的定义：生成树就是包含全部顶点，n-1（n为顶点数）条边都在图里就是生成树

最小：指的是这些边加起来的权重之和最小

2.判定条件：向生成树中任加一条边都一定构成回路

充分必要条件：最小生成树存在那么图一定是连通的，反过来，图是连通的则最小生成树一定存在

3.和最小生成树有关的两个算法：prim算法和kruskal算法

a)prim算法——让小树慢慢长大型算法

按照树的定义，一个顶点就是一棵树。

原理：

1）我们选择一个顶点，也就是选择了一个树。

2）向外找权重最小的边，这样这棵树就有了两个顶点

3）再以这两个顶点向外找权重最小的边，依次循环，知道所有顶点收到树里

举例：

![779158-20160830170004308-171541487.png][]

第一步：选择V1作为顶点

第二步：对比一下与V1相连的各条边的权重，选择最小的V1-V4这条边

第三步：以V1和V4为树，向外找权重最小的边，这时就有了V1-V2,V4-V3两条边，这样就把顶点V2和V3收进了树里。

接着以V1,V2,V3,V4为顶点的树，向外选权值最小的边，注意不能构成回路。依次循环，这样就选择了V4-V7,V7-V5,V7-V6这三条边

数一下现在已经包含了全部的7的顶点，和6条边了，这样最小生成树就长大了

b)kruskal算法——将森林合并为树

原理：

1）和prim算法不一样的是，kruskal算法先选择权重最小的边（因为一个顶点就是一棵树，那么一个边两个顶点就可以看成是一棵树）

2）接着选择剩下的权值比较小的边，注意不能形成回路，只到包含全部顶点

举例：

还是上面那幅图

![779158-20160830170004308-171541487.png][]

第一步：先选择V1-V4,V6-V7两条权值为1的边

第二步：选择V4-V3,V1-V2两条权值为2的边。接着不能选择V4-V2权值为3的边，这样就构成了回路，只能选择V4-V7权值为4的边。

同理不能选择V6-V5权值为5的边，因为会构成回路，只能选择V7-V5权值为6的边。

此时就已经包含了全部的7的顶点，和6条边了，这样最小生成树就从森林变成了树

[779158-20160830164224746-1316460800.png]: /images/20220527/5d5ce53c8c3a42059bc1b5f250fcb066.png
[779158-20160830170004308-171541487.png]: /images/20220527/477caeba979b40e58583d3cea73d537c.png

发表评论取消回复

表情：

评论列表（有 0 条评论，222人围观）

还没有评论，来说两句吧...

相关阅读

相关最小生成树之 Prim算法 & Kruskal算法

1 描述问题：修建一个连接各个小区与煤气供应站点之间的管道，使得造价成本最低，即构造一颗最小生成树。但是如何求解？对应模型：树结构，生成树，最小生成树 2 pr

梦里梦外;/ 2023年02月28日 01:36/ 0 赞/ 104 阅读

相关【经典算法】:图中的最小生成树算法之Prim算法和Kruskal算法

Prim算法 1.概览普里姆算法（Prim算法），图论中的一种算法，可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点（

Love The Way You Lie/ 2022年09月26日 02:58/ 0 赞/ 164 阅读

相关最小生成树-Prim算法和Kruskal算法

Prim算法 1.概览普里姆算法（Prim算法），图论中的一种算法，可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶

悠悠/ 2022年08月21日 06:55/ 0 赞/ 225 阅读

相关算法——最小生成树：Kruskal算法、Prim算法

最小生成树定义：在一个具有V个节点的连通无向图[![G=(E,V)][G_E_V]][G_E_V_G_E_V]中，找到一个子图[![G^\{\\ast \}][G_a

本是古典何须时尚/ 2022年08月11日 18:59/ 0 赞/ 224 阅读

相关最小生成树-Prim算法和Kruskal算法

[最小生成树-Prim算法和Kruskal算法][-Prim_Kruskal] Prim算法 1.概览普里姆算法（Prim算法），图论中的一种算法，可在加权连通图里

「爱情、让人受尽委屈。」/ 2022年06月12日 04:22/ 0 赞/ 255 阅读

相关 H - Highways——最小生成树Kruskal算法+Prim算法

Think: 1知识点：最小生成树Kruskal算法+Prim算法 2思考： 1>多组输入超时，单组输入AC——why??? 2>排序时结构体内重载小于号快于再

水深无声/ 2022年06月11日 07:18/ 0 赞/ 210 阅读

相关最小生成树-Prim算法和Kruskal算法

[https://www.cnblogs.com/biyeymyhjob/archive/2012/07/30/2615542.html][https_www.cnblogs.

骑猪看日落/ 2022年06月02日 03:16/ 0 赞/ 226 阅读

相关最小生成树之prim算法和kruskal算法

在日常生活中解决问题经常需要考虑最优的问题，而最小生成树就是其中的一种。看了很多博客，先总结如下，只需要您20分钟的时间，就能完全理解。比如：有四个村庄要修四条路，让村子能

浅浅的花香味﹌/ 2022年05月27日 10:49/ 0 赞/ 223 阅读

相关 Python之prim与kruskal最小生成树算法

普里姆算法(Prim’s algorithm)：图论中的一种算法，可在加权连通图里搜索最小生成树。即由此算法搜索到的边所构成的树中，不但包括了连通图里的所有顶点，且其所有

àì夳堔傛蜴生んèń/ 2022年02月20日 09:20/ 0 赞/ 255 阅读

相关图之最小生成树 Kruskal算法 Prim算法

一.实际问题最小生成树一般应用在网（带权的图）问题中，实际问题一般比如：　　假设要在n个城市间建立通信联络网，则联通n个城市只需要n-1条线路，但是每两个城市间都

柔光的暖阳◎/ 2021年09月11日 01:30/ 0 赞/ 434 阅读