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

景禹： 小禹禹，今天给大家谈一谈图当中的一个重要概念， 最小生成树（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）是一种使用贪婪方法的最小生成树算法。 该算法初始将图视为森林，图中的每一个顶点视为一棵单独的树。 一棵树只与它的邻接顶点中权值最小且不违反最小生成树属性（不构成环）的树之间建立连边。

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

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

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

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

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

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

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

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

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

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

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

8. 选择边 V_5-V_6 ：添加这条边将导致形成环，舍弃，不添加；
9. 选择边 V_1-V_2 ：添加这条边将导致形成环，舍弃，不添加；
10. 选择边 V_6-V_7 ：没有形成环，则添加：

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

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

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

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

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

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

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

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

2的终点更新为8；

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

0的终点更新为1；

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

将 1的终点更新为5 ；

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

将 5的终点更新为8 ；

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

将 3的终点更新为7 ；

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

将 8的终点更新为6 ；

1. 选择边 V_5-V_6 ：添加这条边将导致形成环 （ V_5 的 终点为6 ， V_6 的 终点为6 ，两个顶点的终点相同则说明添加后会形成环），舍弃，不添加；
   
2. 选择边 V_1-V_2 ：添加这条边将导致形成环（ V_1 的 终点为6 ， V_2 的 终点为6 ，两个顶点的终点相同则说明添加后会形成环），舍弃，不添加；
   
3. 选择边 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 类中没有顶点为止。所走过的顶点和边就是该连通图的最小生成树。

我们同样以下图为栗子进行说明：

假如从顶点 V_0 出发，顶点 V_1 、 V_5 的权值分别为3、4，所以对于顶点 V_0 来说，到顶点 V_1 的权值最小，将顶点 V_1 加入到生成树中：

继续分析与顶点 V_0 和 V_1 相邻的所有顶点（包括 V_2 、 V_5 、 V_6 、 V_8 ），其中权值最小的为 V_5 ， 将 V_5 添加到生成树当中：

继续分析与顶点 V_0 和 V_1 、 V_5 相邻的所有顶点中权值最小的顶点，发现为 V_8 ，则添加到生成树当中。

继续分析与生成树中已添加顶点相邻的顶点中权值最小的顶点，发现为 V_2 ，则添加到生成树中：

重复上面的过程，直到生成树中包含图中的所有顶点，我们直接看接下来的添加过程：

此时算法结束，我们找出了图中的最小生成树。

小禹禹： 景禹，Prim算法的执行过程我懂了，但是我不知道具体该如何实现呢？

Prim算法的实现，和我们刚才所看到的算法思想还是略有不同，就如同理想和现实中存在差距一样。但是我们经过努力总会将理想化为现实。

Prim算法动画演示

Prim算法执行过程。 https://www.zhihu.com/video/1237714308144226304

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，以待使用。
  //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];