最小生成树,Prim算法与Kruskal算法,408方向,思路与实现分析

博主： ZaunEkko
发布时间：2021 年 05 月 31 日
6328次浏览
暂无评论
4732字数
分类：数据结构

# 最小生成树,Prim算法与Kruskal算法,408方向,思路与实现分析

最小生成树,老生常谈了,生活中也总会有各种各样的问题,在这里,我来带你一起分析一下这个算法的思路与实现的方式吧~~

在考研中呢,最小生成树虽然是只考我们分析,理解就行,但我们还是要知道底层是怎么实现的,话不多说,进入正题~~

## 什么是生成树?什么是最小生成树

总所周知,对于一个无向连通图,我们想把他看成一个树的话,那么就不能太乱,也就引出了,如果对于一个生成树(不唯一,满足条件即可),**如果砍去它的一条边,则会变成非连通图,如果加上一条边则会形成一个回路**,也就是包**含图的全部顶点的一个极小连通子图**,如下所示~~

![图片](https://www.zaunekko.com/download/image/MST/1.jpg)

因此,**对于顶点数为n的图,生成树应含有n-1条边**~~

那么,最小生成树又是什么呢?

当边带权时,我们想要一个生成树,使得带权路径和最小,那么这样的生成树就被我们称作最小生成树(不唯一),也就是**边的权值之和最小的生成树**(MST,Minimum-Spanning-Tree)~~

## 那么怎么求一个最小生成树呢?

没错,我们相求一个最小生成树,我们的前辈大牛也想过这个问题,也就引出了两个算法,一个是Prim算法(普里姆),和Kruskal算法(克鲁斯卡尔)~~

先给一个案例我们来分析一下,经典的修路~~

我们想要使得我们这个小镇全都连通,但又花费经济最少(虚线边数值代表所需金钱,也就是权值),该怎么修呢?先给出答案,接下来我们用两个算法分别分析一下思路以及底层实现~~

![图片](https://www.zaunekko.com/download/image/MST/2.jpg)

## Prim算法(普里姆)思路分析与底层实现

Prim算法:从选取的某一个顶点开始,每次将代价最小的新顶点纳入生成树,直到所有顶点都纳入为止~~

思路分析:也就是并查集内加新顶点,为了方便理解,我们把并查集每次都纳入的顶点看成一个在一个圈里加入新顶点,不属于圈里的即为连通的顶点,如图所示算法思路~~

![图片](https://www.zaunekko.com/download/image/MST/3.jpg)

底层实现:我们这里定义两个数组一个为isJoin[]和lowCost[]数组,isJoin[]用来标记是否已加入树,lowCost[]用来表示各节点加入当前树时的最低代价~~

如第一个步骤的时候,只有c点加入了树,那么我们就当c点已经加入了树,也就是说isJoin[6]变为了如表所示(为了方便我们把数组下标换成我们的字母abcdef)~~

|           | C    | A    | B    | D    | E    | F    |
| --------- | ---- | ---- | ---- | ---- | ---- | ---- |
| isJoin[6] | 1    | 0    | 0    | 0    | 0    | 0    |

此时我们的lowCost[6]对应就应为(没有边直接连通则为无穷):

|            | C    | A    | B    | D    | E    | F    |
| ---------- | ---- | ---- | ---- | ---- | ---- | ---- |
| lowCost[6] | 0    | 1    | 5    | 4    | 6    | 4    |

lowCost最小为1,也就是C与A连接所需代价最小,所以当第1步结束时,我们将A连入树中,修改对应isJoin[6]和lowCost[6]~~

|           | C    | A    | B    | D    | E    | F    |
| --------- | ---- | ---- | ---- | ---- | ---- | ---- |
| isJoin[6] | 1    | 1    | 0    | 0    | 0    | 0    |

|            | C    | A    | B    | D    | E    | F    |
| ---------- | ---- | ---- | ---- | ---- | ---- | ---- |
| lowCost[6] | 0    | 0    | 5    | 4    | 6    | 4    |

权:1~~

lowCost最小为4,也就是(D或者F)与圈AC连接所需代价最小,所以当第2步结束时,我们将F连入树中,修改对应isJoin[6]和lowCost[6]~~

|           | C    | A    | B    | D    | E    | F    |
| --------- | ---- | ---- | ---- | ---- | ---- | ---- |
| isJoin[6] | 1    | 1    | 0    | 0    | 0    | 1    |

|            | C    | A    | B    | D    | E    | F    |
| ---------- | ---- | ---- | ---- | ---- | ---- | ---- |
| lowCost[6] | 0    | 0    | 5    | 2    | 6    | 0    |

权:1+4~~

因为现在要和圈ACF连接,D如果想代价最小就可以选择DF连接(2),而不是以前的DC连接(4),2代价更小,这就是**lowCost[]用来表示各节点加入当前树时的最低代价**的意思~~

重复此过程~~

|           | C    | A    | B    | D    | E    | F    |
| --------- | ---- | ---- | ---- | ---- | ---- | ---- |
| isJoin[6] | 1    | 1    | 0    | 1    | 0    | 1    |

|            | C    | A    | B    | D    | E    | F    |
| ---------- | ---- | ---- | ---- | ---- | ---- | ---- |
| lowCost[6] | 0    | 0    | 5    | 0    | 6    | 0    |

权:1+4+2~~

接下来

|           | C    | A    | B    | D    | E    | F    |
| --------- | ---- | ---- | ---- | ---- | ---- | ---- |
| isJoin[6] | 1    | 1    | 1    | 1    | 0    | 1    |

|            | C    | A    | B    | D    | E    | F    |
| ---------- | ---- | ---- | ---- | ---- | ---- | ---- |
| lowCost[6] | 0    | 0    | 0    | 0    | 3    | 0    |

权:1+4+2+5~~

最后

|           | C    | A    | B    | D    | E    | F    |
| --------- | ---- | ---- | ---- | ---- | ---- | ---- |
| isJoin[6] | 1    | 1    | 1    | 1    | 1    | 1    |

|            | C    | A    | B    | D    | E    | F    |
| ---------- | ---- | ---- | ---- | ---- | ---- | ---- |
| lowCost[6] | 0    | 0    | 0    | 0    | 0    | 0    |

权:1+4+2+5+3=15~~

## Kruskal算法(克鲁斯卡尔)思路分析与底层实现

双生关系,Prim是每次选一个连到树里代价最小的顶点构成一个树,Kruskal是每次选一条权值最小的边,使这条边两端连通(如果原本就已经连通就不选),直到所有结点都连通~~

思路分析:上图~~

![图片](https://www.zaunekko.com/download/image/MST/4.jpg)

底层实现:并查集~~

按权值排序~~

| weight | 1    | 2    |
| ------ | ---- | ---- |
| 1      | A    | C    |
| 2      | D    | F    |
| 3      | B    | E    |
| 4      | D    | C    |
| 4      | C    | F    |
| 5      | A    | D    |
| 5      | B    | C    |
| 6      | A    | B    |
| 6      | C    | E    |
| 6      | E    | F    |

依次往下看,1和2两个点是否属于同一集合(先规定所有顶点都属于不同的集合,如果两个顶点相连,则这两个顶点构成了一个集合)~~

如第一次,weight为1,A和C为不同集合,相连,通过~~(集合AC,B,D,E,F)

第二次,weight为2,D和F为不同集合,相连,通过~~(集合AC,DF,B,E)

第三次,weight为3,B和E为不同集合,相连,通过~~(集合AC,DF,BE)

第四次,weight为4,D和C虽然DF是一个集合,AC是一个集合,但DF和AC不是一个集合里的不连通,所以相连,通过~~(集合ACDF,BE)

第五次,weight为4,C和F同属于ACDF集合里,所以不相连,不通过~~(集合ACDF,BE)

第六次,weight为5,A和D同属于ACDF集合里,所以不相连,不通过~~(集合ACDF,BE)

第七次,weight为5,B和C不属于同一个集合里,所以相连,通过~~(集合ABCDEF)

至此成功~~

最小生成树还是简单的,为我们后面学习最短路径做基础,这里大家好好看看,下周我就来谈一谈最短路径的几个算法,这两者很像,但要区分开来~~

最后修改：2021 年 06 月 02 日 03 : 27 PM

END

本文作者： ZaunEkko
文章标题：最小生成树,Prim算法与Kruskal算法,408方向,思路与实现分析
本文地址：https://www.zaunekko.com/archives/14/
版权说明：若无注明，本文皆ZaunEkko原创，转载请保留文章出处。

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

书签网
这张图片很不错
笒鬼鬼
你的文章大图版怎么是这样的，怎么修改的可以分享下？css
笒鬼鬼
站点名称：笒鬼鬼站点链接：https://www.cengui...
笒鬼鬼
站点名称：笒鬼鬼站点链接：https://www.cengui...
TheJan
handsome模板添加服务器状态栏，接口文件，能否发我一下呀？

今日已经过去小时

这周已经过去天

本月已经过去天

今年已经过去个月

最小生成树,Prim算法与Kruskal算法,408方向,思路与实现分析

ZaunEkko • 2021 年 05 月 31 日

# 最小生成树,Prim算法与Kruskal算法,408方向,思路与实现分析

最小生成树,老生常谈了,生活中也总会有各种各样的问题,在这里,我来带你一起分析一下这个算法的思路与实现的方式吧~~

在考研中呢,最小生成树虽然是只考我们分析,理解就行,但我们还是要知道底层是怎么实现的,话不多说,进入正题~~

## 什么是生成树?什么是最小生成树

![图片](https://www.zaunekko.com/download/image/MST/1.jpg)

因此,**对于顶点数为n的图,生成树应含有n-1条边**~~

那么,最小生成树又是什么呢?

## 那么怎么求一个最小生成树呢?

没错,我们相求一个最小生成树,我们的前辈大牛也想过这个问题,也就引出了两个算法,一个是Prim算法(普里姆),和Kruskal算法(克鲁斯卡尔)~~

先给一个案例我们来分析一下,经典的修路~~

![图片](https://www.zaunekko.com/download/image/MST/2.jpg)

## Prim算法(普里姆)思路分析与底层实现

Prim算法:从选取的某一个顶点开始,每次将代价最小的新顶点纳入生成树,直到所有顶点都纳入为止~~

![图片](https://www.zaunekko.com/download/image/MST/3.jpg)

底层实现:我们这里定义两个数组一个为isJoin[]和lowCost[]数组,isJoin[]用来标记是否已加入树,lowCost[]用来表示各节点加入当前树时的最低代价~~

如第一个步骤的时候,只有c点加入了树,那么我们就当c点已经加入了树,也就是说isJoin[6]变为了如表所示(为了方便我们把数组下标换成我们的字母abcdef)~~

|           | C    | A    | B    | D    | E    | F    |
| --------- | ---- | ---- | ---- | ---- | ---- | ---- |
| isJoin[6] | 1    | 0    | 0    | 0    | 0    | 0    |

此时我们的lowCost[6]对应就应为(没有边直接连通则为无穷):

|            | C    | A    | B    | D    | E    | F    |
| ---------- | ---- | ---- | ---- | ---- | ---- | ---- |
| lowCost[6] | 0    | 1    | 5    | 4    | 6    | 4    |

lowCost最小为1,也就是C与A连接所需代价最小,所以当第1步结束时,我们将A连入树中,修改对应isJoin[6]和lowCost[6]~~

|           | C    | A    | B    | D    | E    | F    |
| --------- | ---- | ---- | ---- | ---- | ---- | ---- |
| isJoin[6] | 1    | 1    | 0    | 0    | 0    | 0    |

|            | C    | A    | B    | D    | E    | F    |
| ---------- | ---- | ---- | ---- | ---- | ---- | ---- |
| lowCost[6] | 0    | 0    | 5    | 4    | 6    | 4    |

权:1~~

lowCost最小为4,也就是(D或者F)与圈AC连接所需代价最小,所以当第2步结束时,我们将F连入树中,修改对应isJoin[6]和lowCost[6]~~

|           | C    | A    | B    | D    | E    | F    |
| --------- | ---- | ---- | ---- | ---- | ---- | ---- |
| isJoin[6] | 1    | 1    | 0    | 0    | 0    | 1    |

|            | C    | A    | B    | D    | E    | F    |
| ---------- | ---- | ---- | ---- | ---- | ---- | ---- |
| lowCost[6] | 0    | 0    | 5    | 2    | 6    | 0    |

权:1+4~~

重复此过程~~

|           | C    | A    | B    | D    | E    | F    |
| --------- | ---- | ---- | ---- | ---- | ---- | ---- |
| isJoin[6] | 1    | 1    | 0    | 1    | 0    | 1    |

|            | C    | A    | B    | D    | E    | F    |
| ---------- | ---- | ---- | ---- | ---- | ---- | ---- |
| lowCost[6] | 0    | 0    | 5    | 0    | 6    | 0    |

权:1+4+2~~

接下来

|           | C    | A    | B    | D    | E    | F    |
| --------- | ---- | ---- | ---- | ---- | ---- | ---- |
| isJoin[6] | 1    | 1    | 1    | 1    | 0    | 1    |

|            | C    | A    | B    | D    | E    | F    |
| ---------- | ---- | ---- | ---- | ---- | ---- | ---- |
| lowCost[6] | 0    | 0    | 0    | 0    | 3    | 0    |

权:1+4+2+5~~

最后

|           | C    | A    | B    | D    | E    | F    |
| --------- | ---- | ---- | ---- | ---- | ---- | ---- |
| isJoin[6] | 1    | 1    | 1    | 1    | 1    | 1    |

|            | C    | A    | B    | D    | E    | F    |
| ---------- | ---- | ---- | ---- | ---- | ---- | ---- |
| lowCost[6] | 0    | 0    | 0    | 0    | 0    | 0    |

权:1+4+2+5+3=15~~

## Kruskal算法(克鲁斯卡尔)思路分析与底层实现

思路分析:上图~~

![图片](https://www.zaunekko.com/download/image/MST/4.jpg)

底层实现:并查集~~

按权值排序~~

依次往下看,1和2两个点是否属于同一集合(先规定所有顶点都属于不同的集合,如果两个顶点相连,则这两个顶点构成了一个集合)~~

如第一次,weight为1,A和C为不同集合,相连,通过~~(集合AC,B,D,E,F)

第二次,weight为2,D和F为不同集合,相连,通过~~(集合AC,DF,B,E)

第三次,weight为3,B和E为不同集合,相连,通过~~(集合AC,DF,BE)

第四次,weight为4,D和C虽然DF是一个集合,AC是一个集合,但DF和AC不是一个集合里的不连通,所以相连,通过~~(集合ACDF,BE)

第五次,weight为4,C和F同属于ACDF集合里,所以不相连,不通过~~(集合ACDF,BE)

第六次,weight为5,A和D同属于ACDF集合里,所以不相连,不通过~~(集合ACDF,BE)

第七次,weight为5,B和C不属于同一个集合里,所以相连,通过~~(集合ABCDEF)

至此成功~~

最小生成树还是简单的,为我们后面学习最短路径做基础,这里大家好好看看,下周我就来谈一谈最短路径的几个算法,这两者很像,但要区分开来~~

最小生成树,Prim算法与Kruskal算法,408方向,思路与实现分析

发表评论取消回复

个人博客同步

VSCode配置MSVC+VSCode使用easyx库,2021.5.13日配置~~

KMP算法以及优化(代码分析以及求解next数组和nextval数组)

最小生成树,Prim算法与Kruskal算法,408方向,思路与实现分析

云服务器Apache+MySQL(远程连接)+PHP等环境安装

C++PRIMER第五版练习题答案第一章

KMP算法以及优化(代码分析以及求解next数组和nextval数组)

Java集合方面的小练习(斗地主)

最短路径问题,BFS,408方向,思路与实现分析

VSCode配置MSVC+VSCode使用easyx库,2021.5.13日配置~~

最小生成树,Prim算法与Kruskal算法,408方向,思路与实现分析

发表评论 取消回复

最小生成树,Prim算法与Kruskal算法,408方向,思路与实现分析

发表评论取消回复