图解：什么是最小生成树？

景禹： 小禹禹，今天给大家谈一谈图当中的一个重要概念， 最小生成树（Minimum Spanning Tree） 。

小禹禹： 在景禹之前的一篇文章图解：什么是图？（以“图”话图）中，我看到过生成树的概念，是不是和今天的最小生成树有关系？

景禹： 真聪明，的确关系密切，所以我们简单回顾一下生成树，再来看我们今天的主角。

生成树的定义

一个连通图的生成树是一个极小的连通子图，它包含图中全部的n个顶点，但只有构成一棵树的n-1条边。

可以看到一个包含3个顶点的完全图可以产生3颗生成树。对于包含n个顶点的无向完全图最多包含 $n^{n-2}$ 颗生成树。比如上图中包含3个顶点的无向完全图，生成树的个数为： $3^{3-2}=3$ .

生成树的属性

一个连通图可以有多个生成树；

一个连通图的所有生成树都包含相同的顶点个数和边数；

生成树当中不存在环；

移除生成树中的任意一条边都会导致图的不连通，生成树的边最少特性；

在生成树中添加一条边会构成环。

对于包含n个顶点的连通图，生成树包含n个顶点和n-1条边；

对于包含n个顶点的无向完全图最多包含 $n^{n-2}$ 颗生成树。

景禹： 生成树（Spanning Tree）的内容就这么一丢丢，我想小禹禹都已经掌握了，接下来看我们今天的主角，最小生成树（Minimum Spanning Tree）。

最小生成树

所谓一个 带权图 的最小生成树，就是原图中 边的权值最小的生成树 ，所谓最小是指边的权值之和小于或者等于其它生成树的边的权值之和。

小禹禹： 听起来好绕奥，没有明白.....

景禹： 哈哈，绕很正常。首先你明白最小生成树是和带权图联系在一起的；如果仅仅只是非带权的图，只存在生成树。其他的，我们看栗子解决就好了。

上图中，原来的带权图可以生成左侧的两个最小生成树，这两颗最小生成树的权值之和最小，且包含原图中的所有顶点。

小禹禹： 看图就是清晰，一下子理解了，但我们又如何从原图得到最小生成树呢？

景禹： 这个确实是个问题，还是个好问题。最小生成树算法有很多，其中最经典的就是克鲁斯卡尔（Kruskal）算法和普里姆（Prim）算法，也是我们考试、面试当中经常遇到的两个算法。

Kruskal算法

克鲁斯卡尔算法（Kruskal）是一种使用贪婪方法的最小生成树算法。该算法初始将图视为森林，图中的每一个顶点视为一棵单独的树。一棵树只与它的邻接顶点中权值最小且不违反最小生成树属性（不构成环）的树之间建立连边。

小禹禹： 这我哪儿能听懂？能不能具体一点儿？

景禹： 那就让我们一起与愉快地开始看例子，学算法吧！

第一步：将图中所有的边按照权值进行非降序排列；

第二步：从图中所有的边中选择可以构成最小生成树的边。

选择权值最小的边 $V_4-V_7$ ：没有环形成，则添加：

选择边 $V_2-V_8$ ：没有形成环，则添加：

选择边 $V_0-V_1$ ：没有形成环，则添加：

选择边 $V_0-V_5$ ：没有形成环，则添加：

选择边 $V_1-V_8$ ：没有形成环，则添加：

选择边 $V_3-V_7$ ：没有形成环，则添加：

选择边 $V_1-V_6$ ：没有形成环，则添加：

此时已经包含了图中顶点个数9减1条边，算法停止。

小禹禹： 原来这样也可以，但我有一个问题，我们该如何判断添加一条边后是否形成环呢？

要判断添加一条边 X-Y 是否形成环，我们可以判断顶点X在最小生成树中的终点与顶点Y在最小生成树中的 终点是否相同 ，如果相同则说明存在环路，否则不存环路，从而决定是否添加一条边。

所谓终点，就是将所有顶点按照从小到大的顺序排列好之后；某个顶点的终点就是"与它连通的最大顶点"。看下图，我们可以对图中顶点进行排序，排序后的顶点存放在一个数组中，每一个顶点则对应一个下标，同样的我们针对排序后的数组创建一个顶点的终点数组，初始时图中的每一个顶点是一棵树，每一个顶点的终点初始化为自身，我们用0来表示。

回到之前的算法执行过程，我们配合这个终点数组再来一次。

选择权值最小的边 $V_4-V_7$ ：没有环形成（ $V_4$ 的终点为4， $V_7$ 的终点为7），则添加，并更新终点数组：

此时发现4的终点更新为7；

选择边 $V_2-V_8$ ：没有形成环（ $V_2$ 的终点为2， $V_8$ 的终点为8），则添加，并更新终点数组：

2的终点更新为8；

选择边 $V_0-V_1$ ：没有形成环（ $V_0$ 的终点为0， $V_1$ 的终点为1），则添加，并更新终点数组：

0的终点更新为1；

选择边 $V_0-V_5$ ：没有形成环（ $V_0$ 的 终点为1 ， $V_5$ 的 终点为5 ），则添加，并更新终点数组：

将 1的终点更新为5 ；

选择边 $V_1-V_8$ ：没有形成环（ $V_1$ 的 终点为5 ， $V_8$ 的 终点为8 ），则添加，并更新数组：

将 5的终点更新为8 ；

选择边 $V_3-V_7$ ：没有形成环（ $V_3$ 的 终点为3 ， $V_7$ 的 终点为7 ），则添加，并更新数组：

将 3的终点更新为7 ；

选择边 $V_1-V_6$ ：没有形成环（ $V_1$ 的 终点为8 ， $V_6$ 的 终点为6 ），则添加，并更新终点数组：

将 8的终点更新为6 ；

选择边 $V_5-V_6$ ：添加这条边将导致形成环（ $V_5$ 的 终点为6 ， $V_6$ 的 终点为6 ，两个顶点的终点相同则说明添加后会形成环），舍弃，不添加；

选择边 $V_1-V_2$ ：添加这条边将导致形成环（ $V_1$ 的 终点为6 ， $V_2$ 的 终点为6 ，两个顶点的终点相同则说明添加后会形成环），舍弃，不添加；

选择边 $V_6-V_7$ ：没有形成环（ $V_6$ 的 终点为6 ， $V_7$ 的 终点为7 ），则添加：

将 **6的终点更新为7**；此时已经包含了图中顶点个数9减1条边，算法停止。
小禹禹： 景禹，算法的整体过程我明白了，现在能给我分析一下实现吗？
int Find(int *parent, int f)
	while( parent[f] > 0 )
		f = parent[f];
	return f;
// Kruskal算法生成最小生成树
void MiniSpanTree_Kruskal(MGraph G)
	int i, n, m;
	Edge edges[MAGEDGE];	// 定义边集数组
	int parent[MAXVEX];		// 定义parent数组用来判断边与边是否形成环路
	int eCount = 0;
	for( i=0; i < G.numVertexes; i++ )
		parent[i] = 0;
	for( i=0; i < G.numEdges; i++ )
		n = Find(parent, edges[i].begin);	// 4 2 0 1 5 3 8 6 6 6 7
		m = Find(parent, edges[i].end);		// 7 8 1 5 8 7 6 6 6 7 7
		if( n != m )		// 如果n==m，则形成环路，不满足！
			parent[n] = m;	// 将此边的结尾顶点放入下标为起点的parent数组中，表示此顶点已经在生成树集合中
			printf("(%d, %d) %d ", edges[i].begin, edges[i].end, edges[i].weight);
			++eCount;
			if( eCount == (G.numVertexes-1)){
				break;
复制代码
时间复杂度分析
O(ElogE)或者O(ElogV)，其中E代表图中的边的数目，V代表图中的顶点数目。对图中的边按照非降序排列需要O(ElogE)的时间。排序后遍历所有的边并判断添加边是否构成环，判断添加一条边是否构成环最坏情况下需要O(logV)，关于这个复杂度等到景禹给你们谈并查集的时候再分析；因此，总的时间复杂度为O(ElogE + ElogV)，其中E的值最大为V(V-1)/2，因此O(logV) 等于 O(logE)。因此，总的时间复杂度为O(ElogE) 或者O(ElogV)。
Prim算法
普里姆算法在找最小生成树时，将顶点分为两类，一类是在查找的过程中已经包含在生成树中的顶点（假设为 A 类），剩下的为另一类（假设为 B 类）。
对于给定的连通网，起始状态全部顶点都归为 B 类。在找最小生成树时，选定任意一个顶点作为起始点，并将之从 B 类移至 A 类；然后找出 B 类中到 A 类中的顶点之间权值最小的顶点，将之从 B 类移至 A 类，如此重复，直到 B 类中没有顶点为止。所走过的顶点和边就是该连通图的最小生成树。
我们同样以下图为栗子进行说明：
假如从顶点  出发，顶点  、 的权值分别为3、4，所以对于顶点  来说，到顶点  的权值最小，将顶点  加入到生成树中：
继续分析与顶点  和  相邻的所有顶点（包括  、、、 ），其中权值最小的为  ， 将  添加到生成树当中：
继续分析与顶点  和  、 相邻的所有顶点中权值最小的顶点，发现为  ，则添加到生成树当中。
继续分析与生成树中已添加顶点相邻的顶点中权值最小的顶点，发现为  ，则添加到生成树中：
重复上面的过程，直到生成树中包含图中的所有顶点，我们直接看接下来的添加过程：
此时算法结束，我们找出了图中的最小生成树。
小禹禹： 景禹，Prim算法的执行过程我懂了，但是我不知道具体该如何实现呢？
Prim算法的实现，和我们刚才所看到的算法思想还是略有不同，就如同理想和现实中存在差距一样。但是我们经过努力总会将理想化为现实。
Prim算法动画演示
Prim算法代码实现
// Prim算法生成最小生成树
void MiniSpanTree_Prim(MGraph G)
	int min, i, j, k;
	int adjvex[MAXVEX];		// 保存相关顶点下标
	int lowcost[MAXVEX];	// 保存相关顶点间边的权值
	lowcost[0] = 0;			// V0作为最小生成树的根开始遍历，权值为0(0,3,*,*,*,4,*,*,*)
	adjvex[0] = 0;			// V0第一个加入
	// 初始化操作
	for( i=1; i < G.numVertexes; i++ )
		lowcost[i] = G.arc[0][i];	// 将邻接矩阵第0行所有权值先加入数组
		adjvex[i] = 0;				// 初始化全部先为V0的下标
	// 真正构造最小生成树的过程
	for( i=1; i < G.numVertexes; i++ )
		min = INFINITY;		// 初始化最小权值为65535等不可能数值
		j = 1;
		k = 0;
		// 遍历全部顶点
		while( j < G.numVertexes )
			// 找出lowcost数组已存储的最小权值
			if( lowcost[j]!=0 && lowcost[j] < min )
				min = lowcost[j];
				k = j;		// 将发现的最小权值的下标存入k，以待使用。
			j++;
		//K的取值依次为：1,5,8,2,6,7,4,3
		// 打印当前顶点边中权值最小的边
		printf("(%d,%d)", adjvex[k], k);(0,1)
		lowcost[k] = 0;		// 将当前顶点的权值设置为0，表示此顶点已经完成任务，进行下一个顶点的遍历(0,0,*,*,*,4,*,*,*)
		// 邻接矩阵k行逐个遍历全部顶点(k=1,)
		for( j=1; j < G.numVertexes; j++ )
			if( lowcost[j]!=0 && G.arc[k][j] < lowcost[j] )
				lowcost[j] = G.arc[k][j];
				adjvex[j] = k;	
复制代码
时间复杂度分析
上面的代码中，当 i == 1的时候，内层的 while 与 for 循环中 j 的取值范围是从 1 到 n-1，内循环一共计算了 2(n-1) 次，其中n为图中的顶点个数；
当 i == 2 的时候，内层循环还是一共计算 2(n-1) 次；
以此类推......
i 取最大值 n -1，内层循环还是一共计算 2(n-1) 次；
所以，整体的执行次数就是 (n-1) * 2(n-1)，Prim算法的复杂度是  级别的。
某公司规模不断扩大，在全国各地设立了多个分公司，为了提高公司的工作效率，使各分公司之间的信息可以更快、更准确的进行交流，该公司决定要在各分公司之间架设网络，由于地理位置和距离等其他因素，使各个分公司之间架设网线的费用不同，公司想各分公司之间架设网线的费用降到最低，那么应该怎样来设计各分公司及总公司之间的线路？该公司的所有分公司及总公司的所在位置如下图所示，顶点代表位置及公司名称，边表示可以架设网线的路线，边上的数字代表架设该网线所需要的各种花费的总和。这样就构成了一个带权的连通图，从而问题就转化为求所得到的带权连通图的最小生成树。
这个题目，景禹就不在这里再废话了，你们自己有时间练习奥，两种算法都试一试。
应用案例二
LeetCode 1135. 最低成本联通所有城市 (Connecting Cities With Minimum Cost)
想象一下你是个城市基建规划者，地图上有 N 座城市，它们按以 1 到 N 的次序编号。
给你一些可连接的选项 conections，其中每个选项 conections[i] = [city1, city2, cost] 表示将城市 city1 和城市 city2 连接所要的成本。（连接是双向的，也就是说城市 city1 和城市 city2 相连也同样意味着城市 city2 和城市 city1 相连）。
返回使得每对城市间都存在将它们连接在一起的连通路径（可能长度为 1 的）最小成本。该最小成本应该是所用全部连接代价的综合。如果根据已知条件无法完成该项任务，则请你返回 -1。
示例 1：
输入：N = 3, conections = [[1,2,5],[1,3,6],[2,3,1]]
选出任意 2 条边都可以连接所有城市，我们从中选取成本最小的 2 条。
示例 2：
输入：N = 4, conections = [[1,2,3],[3,4,4]]
输出：-1
即使连通所有的边，也无法连接所有城市。
1 <= N <= 10000
1 <= conections.length <= 10000
1 <= conections[i][0], conections[i][1] <= N
0 <= conections[i][2] <= 10^5
conections[i][0] != conections [i][1]
我们以示例1为例，其中输入N=3，表示图中包含3个顶点，conections = [[1,2,5],[1,3,6],[2,3,1]]，[1,2,5]表示顶点1和2的权值为5，根据输入可以得到下图：
看到这里，小禹禹一定会说，这有什么难的，不就是找一个带权联通图的最小生成树吗？的确如此，所以各位小禹禹们有时间可以作为练习，巩固一下Prim和Kruskal算法。
示例二中，输入N = 4, conections = [[1,2,3],[3,4,4]]，返回-1，因为这个输入本身就是一个非联通图，所以怎么可能在图中找出一个从每个顶点到其他顶点的路径呢？不存在返回-1。
哈哈，景禹就不在这里放代码了，祝你们自己写的代码AC（其实只需要对Prim和Kruskal算法代码进行微调）。
最小生成树的问题，简单得理解就是给定一个带有权值的连通图（连通网），从众多的生成树中筛选出权值总和最小的生成树，即为该图的最小生成树。
最经典的两个最小生成树算法： Kruskal 算法与 Prim 算法。两者分别从不同的角度构造最小生成树，Kruskal 算法从边的角度出发，使用贪心的方式选择出图中的最小生成树，而 Prim 算法从顶点的角度出发，逐步找各个顶点上最小权值的边来构建最小生成树的。
最小生成树问题应用广泛，最直接的应用就是网线架设、道路铺设。还可以间接应用于纠错的LDPC码、Renyi 熵图像配准、学习用于实时脸部验证的显著特征、减少蛋白质氨基酸序列测序中的数据存储，在湍流（turbulent）中模拟粒子交互的局部性，以及用于以太网桥接的自动配置，以避免在网络中形成环路。除此之外，最小生成树在聚类算法中也是应用广泛。
所以一定要搞懂最小生成树、Kruskal 算法及Prim 算法奥！！！记得给景禹点击一下右下角的在看，给点掌声和鼓励！
欢迎关注景禹的个人公众号，获取更多优质内容。