m数据结构 day14 图（四）最小生成树（Prim VS Kruskal）

最小生成树 Minimum Cost Spanning Tree（被完美解决的最优化问题）

Minimum Cost Spanning Tree直译过来是最小代价生成树，因为一定要涉及权。最小生成树是针对网的，即必须有权值，“最小”一词是一个优化目标，就是要保证生成树的权值之和最小。

最小生成树的目的很简单，就是要在一个网中，找到一棵树，使得这棵树包含所有顶点，且任意两个顶点之间可以互达，且n-1条边的权的和要最小。

抽象起来就这么一回事，但是现实中却有很多需要用到最小生成树的应用。比如为9个村庄建设公路，保证9个村庄互通，并且总的公路长度最短，以节省修路费用和后期通行费用时间等；再比如为这9个村庄搭建网络，相当于是建设信息高速公路嘛，其实和修路是一个问题。总之就是要拿出最节省成本或者时间的一个能够实现功能的方案，这是典型的最优化问题。

幸运的是，找到最小生成树不是一个NP难问题，而是一个可以被完美解决的最优化问题，即一定可以精确找到最优的这棵最小生成树。并且有两种经典的算法，prim算法和kruskal算法。

我看了B站这个视频，一下就对这两个算法的原理有了理解，至少是会用了。这个视频的ppt做的超级好看，并且讲解也是异常清晰，墙裂推荐。

（超简单！全局意识）克鲁斯卡尔算法 Kruskal， $O(e\log e)$，使用边集数组存储结构,适用于边少的稀疏图

克鲁斯卡尔算法是图论考试时找最小生成树的必用算法，反正只要遇到找最小生成树的题目，我直接用克鲁斯卡尔，因为他的规则实在是太简单了，小学生都能立刻学会怎么用，当然要证明为什么这样一定能得到最小生成树的证明他们就不会了。由于他更简单，所以先说它。

相比于prim算法，kruskal算法更有全局意识，直接从图的最短权值的边入手找答案。针对边展开。他是一上来就把所有边按照权值排好顺序，然后直接找最短的用来生成一棵树，依次找稍微长点的但是不会在已生成的树中构成环的边，直到生成一棵树。

以这个图为例：

• 首先把图的所有边用边集数组存起来
  

• 并且根据权值从小到大进行排序
  

• 然后依次取出边序列中排在最前面的边，每次取出的边放入生成树后都判断一下是否成环，如果没有成环，则继续操作；如果成环，则抛弃这条边，直接取边序列的下一条边，比如下图中，顶点6到顶点8的这条权值为6的边放入生成树，成环了，所以直接丢弃这条边，取边序列的下一条边：点7到点8的权值为7的边。但是这条边显然还是会成环，所以继续抛弃，取2-3，不成环，再继续取0-7，成环，抛弃，取1-2······

• 每次还要判断边数是否达到N-1,即是否已经是树，如果是，则不再继续取，至此就得到最小生成树。
  

代码

代码中为了判断新边加入是否成环，要用到一个parent数组，理解起来稍微困难点。

parent数组的初始值为全0。

parent[n]=m,表示从顶点n出发，在当前生成树中能到达的路径末端的顶点是m。

用parent数组判定新边的加入是否会导致现有生成树中出现环的根本依据：如果从两个顶点出发，能够走到同一个末端顶点，那么他俩就在一条路径上，如果把他俩连起来，就会形成环路。这是很好理解的，尤其是学过图论之后。

举个例子以便理解，用上面的9个顶点的图做示例，一共9个点，所以最小生成树有8条边，我把8条边的依次加入做成一张图，便于观看parent数组的变化：

• 由上面的排好序的边数组，权值最小的第一条边是6-7，parent[6]=0,所以Find返回的n是6自己；parent[7]=0,所以Find返回的m是7自己，所以parent[n]=m,即parent[6]=7，意思是在当前的生成树，从6出发，能到达的末端顶点是7
• 第二条边是2-8，parent[2]=0,所以Find返回的n是2自己，同理m也是8自己，所以parent[2]=8，意思是在当前的生成树，从2出发，能到达的末端顶点是8
• 边3是5-6，parent[5]=0,s所以返回的n是5自己；parent[6]=7，所以按照Find函数的逻辑，f=parent[f]=7,而parent[7]是0，所以返回的m是7，所以这条边的加入置parent[5]为7，意思是在当前的生成树，从5出发，能到达的末端顶点是7
• 边4是0-1，parent[0]和parent[1]都是0，所以返回的n=0,m=1,parent[0]=1,意思是在当前的生成树，从0出发，能到达的末端顶点是1
• 边5是2-5，parent[2]=8,而parent[8]=0,所以返回n=8;parent[5]=7，而parent[7]=0,所以返回的m是7,；所以置parent[8]为7，意思是在当前的生成树，从8出发，能到达的末端顶点是7
• 下一条边是6-8，但是parent[6]是7，而parent[7]是0，所以n=7;parent[8]=7,所以m=7;n=m，所以这条边加入要成环，因此舍弃这条边，继续下一条的判断。

注意最后一个加入的顶点的parent数组值不会被更新，仍然是0，这里即parent[4]

生成最小生成树的步骤图，边上的圆括号里是该边被加入的顺序，没有画边的权值

/*kruskal算法生成最小生成树*/
#define MAXEDGE 100
#define MAXVEX 20
#define INF 65535
void MiniSpanTree_Kruskal(MGraph * G)//传入图的邻接矩阵
{Edge edges[MAXEDGE];int parent[MAXVEX];AdjToEdges(G, edges);//把邻接矩阵转化为边集数组SortEdges(edges);//把边集数组按照权值排序int i;for (i=0;i<G->numV;++i)parent[i] = 0;//初始化int m, n;for (i=0;i<G->numE;++i)//对每一条边进行循环{n = Find(parent, edges[i].begin);m = Find(parent, edges[i].end);if (n != m)//则edges[i]的加入不会导致生成树中有环{parent[n] = m;//加入edges[i]边，起点是n，终点是mprintf("(%d, %d) %d ", edges[i].begin, edges[i].end, edges[i].weight);}}
}/*把邻接矩阵转化为边集数组*/
void AdjToEdges(MGraph * G, Edge * edges)
{int i, j, k;k = 0;//k是已添加到边集数组的边数for (i = 0;i<G->numV;++i){for (j=0;j<G->numV;++j){if (G->arc[i][j] != INF){edges[k].begin = i;edges[k].end = j;edges[k++].weight = G->arc[i][j];}}}
}/*把边集数组按照权值排序*/
void SortEdges(Edge * edges)
{}/*返回在当前生成树中，从顶点f出发，能到达的路径的末端的顶点索引 //如果顶点f还不在生成树中,则parent[f]==0，返回f*/
void Find(int * parent, int f)
{while (parent[f]>0)//parent[f]>0则f-parent[f]是一条已经加入到最小生成树的边，f是起点f = parent[f];return f;
}

分析时间复杂度（顶点数n,边数e）：

• 第一个for执行n次
• 第二个for执行e次，但是里面有两次调用Find函数
• Find函数里面有while循环，时间复杂度是 $\log e$,这是为什么？？没懂

所以总的时间复杂度是 $O(e \log e)$,低次项n被省略了。

所以kruskal算法很适合点多但是边少的图，即稀疏图。

普利姆算法(走一步看一步) Prim, $O(n^2)$，适用于边多的稠密图

他是以某一个顶点开始出发，走一步看一步（找已选顶点所连接到的所有边的权值最小者，以生长树和拓展已选顶点集合)的思维方式，逐步生成最小生成树。

要用到顶点集合的两个子集，一个是已选顶点集合（下图中的U），另一个是未选顶点集合（下图中的V-U）。

要用到三个长度为顶点个数n的数组来辅助:

• selected：表示顶点是否已经被选，初始值全为false
• minDist: 存储某一时刻连接已选顶点集合U到未选顶点集合V-U的所有边的权值最小值，初始值全为inf
• parent：父亲列表，存储了最小权值边的两个顶点信息。parent[i]-i是一条被选中以构建最小生成树的边。parent[i]是指向第i个顶点的边的另一个顶点。初始值全为-1。
  

prim算法过程：
从任意一个顶点出发，把这个顶点作为已选顶点集合U，更新三个列表的值，比如如果选择第一个点为 $v_0$，则selected[0]更新为true，且minDist[1]更新为4，minDist[7]更新为8。然后选择和已选顶点集合相连的这些边中的权值最小者，在这里就是4，即顶点1进入已选顶点集合U，更新parent[1]为0，表示0-1这条边被加入到了最小生成树。

权之和是37。

在用prim算法找最小生成树的过程中，由于每一次要在已选顶点集合U的所有关联到的边中找权值最小者，所以有点难找，对于上图这种小图手工执行起来比kruskal稍微难一点，容易出错一点。

代码,使用邻接表

由于一般没有边的权值为0，所以这个代码把minDist[i]置0表示顶点i被选了，即相当于selected[i]为true，所以这里就不再需要专门拿一个selected数组了，让minDist数组兼任。

$minDist[j]==0$则j属于已选顶点集合U，否则属于未选顶点集合V-U。

#define INF 65535
#define MAXVEX 100
void MiniSpanTree_Prim(MGraph *G)
{int i;/*bool selected[MAXVEX];//初始化三个辅助数组for (i=0;i<G->numV;++i){selected[i] = false;minDist[i] = INF;parent[i] = -1;}selected[0] = true;//把v0加入已选顶点集合*/int minDist[MAXVEX];int parent[MAXVEX];//parent[i]-i是一条最小生成树中的边，parent[i]是边的起点for (i=1;i<G->numV;++i)//循环除了v0外的所有顶点，即所有未选顶点{minDist[i] = G->arc[0][i];//扫描邻接矩阵第0行，并把v1开始的所有顶点到v0的距离（权值）存起来parent[i] = 0;//把v1-vn的起点都初始化为v0}int min, j, k;for (i=1;i<G->numV;++i){min = INF;j = 1;k = 0;while (j < G->numV){if (minDist[j]!=0 && minDist[j]<min)//如果顶点j没有进入已选顶点集合且v0和vj的边的//权值小于当前最小值min，则把0-j这条边认为是当前最小权值边{min = minDist[j];k = j;//k存储到v0权值最小的边的除v0外的另一个顶点的下标}++j;}printf("(%d, %d) ", parent[k], k);//打印当前顶点边中的权值最小边，parent[k]-k,即0-kminDist[k] = 0;//把顶点k的权值置为0，表示顶点k被选入已选顶点集合，相当于设置selected[k]=true;//刚把顶点k选入，现在把邻接矩阵第k行的权值存入minDist,把未选顶点的parent[j]设为k//相当于从k开始找下一个点，这和代码开头的第一个for功能一样for (j=1;j<G->numV;++j){if (minDist[j]!=0 && G->arc[k][j]<minDist[j])//这时候要权值G->arc[k][j]小于minDist中对应位置已有值minDist[j]才更新minDist[j]//这就保证了更新的一定是从已选顶点集合的所有顶点出发到顶点j的最短边的权值{minDist[j] = G->arc[k][j];parent[j] = k;}}}
}

分析一下时间复杂度（n为顶点数）：

• 开头第一个for语句有n-1次操作
• 第二个for也是n-1次，但是里面嵌套了一个while和一个for，嵌套while执行次数是n-1, 嵌套for执行次数是n-1。所以第二个for的操作次数为 $(n-1)\times (n-1+n-1)=2(n-1)^2$

总操作次数是 $2(n-1)^2+n-1$,用大O表示法，省略低次项和系数，时间复杂度是 $O(n^2)$。

所以prim算法很适合点少的图，边多少不影响复杂度，所以很适合稠密图。