图的最小生成树之克鲁斯卡尔算法
编辑时间:2016-08-13 赞：10 踩：0
导言：
本文将会讲解最小生成树的相关知识、克鲁斯卡尔算法的原理，及其实现。同时也会附上POJ2485的题解，POJ2485这道题是一道关于求取图的最小生成树的OJ题。另外，本文也会稍微提及一下有关并查集的相关知识，因为这是讲解克鲁斯卡尔算法绕不开的一个重点，但限于篇幅不会过于深入。正文：
本文适合于有一定树、图论基础知识的人阅读。如果不了解图论的基础知识的话，就赶紧去恶补吧。因为图是一种非常有用、有意思的数据结构。一、最小生成树（Minimum Spanning Tree）
在一给定的无向图 G = (V, E) 中，(u, v) 代表连接顶点 u 与顶点 v 的边（即 ），而 w(u, v) 代表此边的权重，若存在 T 为 E 的子集（即 ）且为无循环图，使得 的 w(T) 最小，则此 T 为 G 的最小生成树。 最小生成树其实是最小权重生成树的简称。（摘自百度百科）
上面是最小生成树的严格定义。通俗来讲，对于一个给定的带权无向连通图,选取一棵生成树,使树上所有边上权的总和为最小，这棵树就叫最小生成树（简称MST）。
这里要注意的是，只有带权无向连通图才会有最小生成树。如果是有向的，那么正向和反向的最小生成树可能会不一致。如果是不连通的那么总会有任意个（≥1）顶点，不在树内，不符合最小生成树的定义。
（图片来自维基百科）
上图中黑色粗线标出来的便是该图的最小生成树，该树包含了该图的所有顶点。不难发现，树上的所有节点都是彼此连通的。虽然整棵树的边的权值之和为最小，但这并不能确保树上的任意两个节点间的距离（权值之和）最小。关于图的两点间最短距离的求解，便是另外一个图论中很常见的问题----图的最短路径求解。图的最小生成树与最短路径的求解是初学者非常容易混淆的图的两个基础知识。
二、克鲁斯卡尔算法（Kruskal）
关于求解图的最小生成树，有两个非常经典的算法，一个是普里姆（Prim）算法，另一个便是今天的主角，克鲁斯卡尔算法算法。关于普里姆算法，我会另写一篇博文来讲解。
以下为克鲁斯卡尔算法的定义：
假设 WN=(V,{E}) 是一个含有 n 个顶点的连通网，则按照克鲁斯卡尔算法构造最小生成树的过程为：先构造一个只含 n 个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它是一个含有 n 棵树的一个森林。之后，从网的边集 E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直至森林中只有一棵树，也即子图中含有 n-1条边为止。（摘自百度百科）
由上述定义可知，克鲁斯卡尔算法运用到了贪心的思想，每次都从没被遍历的边集中寻找权值最小的边，判断边上的两个点是否在同一棵树上（同一个集合内）。如果不在同一棵树上（同一个集合内），就把这两个节点相连；如果在同一棵树，证明连接这两个节点会使树形成回环，破坏树的结构，所以要把这条边抛弃。如此反复，直至所有节点都在同一棵树上（同一个集合内）。此时，这棵树有n个节点，n-1条边。
借用维基百科的例子解释，相信大家会对卡鲁斯卡尔算法有更形象的认识。
图①
图②
图③
图④
图⑤
图⑤中，BC边和EF边的权值为8。是未遍历的边集中权值最小的，但是由于这两条边上的节点B、C、E、F已经在同一棵树上，所以要舍弃这两条边，从而选取权值为9的EG边，把边上的节点加入树（集合）中。从而演变成图⑥的样子，最终构成一颗最小生成树。
图⑥
对克鲁斯卡尔算法的原理有一个感性的认识后，下一步要做的便是按照卡尔鲁斯卡尔算法的原理来实现具体的源代码。
由于每次都是从未被遍历的边集中选取权值最小的边，所以我们可以一开始便把所有的边按权值进行排序，然后按顺序遍历，这样就能提高边的选取效率。因此，克鲁斯卡尔算法的效率会受到排序算法效率的影响。在我给出的代码中，我会选取快速排序算法作为排序算法。
选取了边之后，便要判断边上的两个节点是否位于一棵树上（一个集合内）。这里需要用到并查集的知识。关于并查集的知识，我向大家推荐一篇文章，传送门：http://www.cnblogs.com/cyjb/p/UnionFindSets.html
并查集，是一种简单的树形数据结构，主要用于解决与树和图的连通性相关的问题，例如查找一棵树的根节点，判断两个节点是否是连通的。
那么，并查集是如何实现的？每个集合可能包含一个或多个元素，并选出集合中的某个元素作为代表（根节点）。每个集合中具体包含了哪些元素是不关心的，具体选择哪个元素作为代表一般也是不关心的。我们关心的是，对于给定的元素，可以很快的找到这个元素所在的集合的代表元素，以及合并两个元素所在的集合，而且这些操作的时间复杂度都是常数级的。
也就是说，在判断连通性的问题上，代表元素（根节点）代表了整个集合，从外部来看，整个集合只有一个代表元素，因此，代表元素在一个集合内必须是唯一的。如果两个元素的所处集合的代表元素元素一致，便可以证明这两个元素便处于一个集合内，这两个元素是连通的。
并查集的操作包括建立并查集，查找集合内的代表元素（根节点），以及合并并查集。
1 .并查集的建立与存储
可以用数据来存放并查集。集合内的每一个元素（节点）为下标，存放该元素的父元素（前驱节点或父节点）。
2 .集合内代表元素（根节点）的查找
当一个元素的存放的父元素（前驱节点）为自身时，它便是代表元素（根节点）。
3 .合并并查集
最简单的做法便是，把一个并查集的代表元素（根节点）的父节点指向另一个并查集的代表元素（根节点），这样原并查集的代表元素（根节点）便指向了另一个元素的代表元素（根节点），两个集合的代表元素（根节点）便是同一个了。
当然，这里还涉及到并查集的压缩存放和合并策略，这里就不展开细讲了。感兴趣的可以看一下我上面提到的那一篇文章。
回到克鲁斯卡尔算法。根据上面提到的并查集知识，不难发现，我可以利用并查集来判断一条边上的两个节点是否在同一棵树上（同一个集合内）。
总的来说，整个代码就分为以下几个步骤：
1. 按边的权值对所有的边进行排序
2. 从未被遍历的边集中选出最小边
3. 用并查集判断该边的两个节点是否在同一棵树（同一个集合）内。
4. 若两个节点在同一棵树上，抛弃该边；否则，将两个节点的加入至同一个集合中，同时合并它们的并查集。
5. 重复步骤1-4，直至所有节点位于同一个集合。
下面，上代码：
#include
#define INFINITY 65535
//定义节点数
#define VERTEXT_NUMBER 6
//要用到并查集的知识，因为要查找两个节点是否在同一棵树中
//该结构体专门由于存储边
typedef struct edge{
int begin;
int end;
int weight;
}Edge;
int graph[VERTEXT_NUMBER][VERTEXT_NUMBER] = {
{0,6,1,5,INFINITY,INFINITY},
{6,0,5,INFINITY,3,INFINITY},
{1,5,0,5,6,4},
{5,INFINITY,5,0,INFINITY,2},
{INFINITY,3,6,INFINITY,0,6},
{INFINITY,INFINITY,4,2,6,0},
};
//按边集的方式存储图，一个有n个节点的至多只有n*n条边
Edge graEdge[ (VERTEXT_NUMBER * VERTEXT_NUMBER)];
//存储最小生成树，按边集的方式存储
Edge treeEdge[VERTEXT_NUMBER];
//并查集
int preNode[VERTEXT_NUMBER];
/** void quicksort(long *arr,int start,int last)
*\brief 快速排序，在原数组的基础上进行排序
*
* \param start：进行排序的数组的起点下标
* \param last：进行排序的数组的终点下标,排序数组包含该下标的元素
* \return 无
*
*/
void quicksort(Edge *arr,int start,int last){
if(start>=last){
return ;
}
int left=start,right=last,pos=start+1;
Edge tmp,pivotValue=arr[start];
while(left!=right){
if(arr[pos].weight>pivotValue.weight){
//由于两个数进行了交换，pos位置的值是新值，所以不用后移
tmp=arr[right];
arr[right--]=arr[pos];
arr[pos]=tmp;
}else{
arr[left++]=arr[pos];
pos++;
}
}
arr[left]=pivotValue;
quicksort(arr,start,left-1);
quicksort(arr,left+1,last);
}
//查找并查集中的祖先元素
int find(int nodeA){
int anceA=preNode[nodeA],tmp;
//如果他不是根节点，循环，直至找到根节点
while(anceA != preNode[anceA]){
anceA = preNode[anceA];
}
//压缩并查集，让一课集合内的节点都指向一个根（代表元素）
while(anceA != preNode[nodeA]){
tmp = preNode[nodeA];
preNode[nodeA] = anceA;
nodeA = tmp;
}
return anceA;
}
//合并两个集合的根节点（代表元素）
void merge(int unionA,int unionB){
preNode[unionB] = unionA;
}
int Kruskal(){
int treeWeight = 0;
int edgeCnt=0; //记录已遍历多少条边
int treeEdgeCnt = 0;
int beParent,endParent;
for(int i= 0 ; i < VERTEXT_NUMBER ;i++){
//初始化并查集
preNode[i] = i;
}
//最小生成树有n-1条边，n为节点数
while( treeEdgeCnt < (VERTEXT_NUMBER-1)){
//如果这条边上的两个节点的祖先不一样，把它们相连，它们的相连不会造成回环，以为它们属于不同的树（集合）
if( (beParent = find(graEdge[edgeCnt].begin)) != (endParent = find(graEdge[edgeCnt].end)) ){
treeEdge[treeEdgeCnt] = graEdge[edgeCnt];
treeEdgeCnt++;
treeWeight += graEdge[edgeCnt].weight;
merge(graEdge[edgeCnt].begin,graEdge[edgeCnt].end);
printf("treeWeight:%d\n",treeWeight);
}
edgeCnt++;
}
return treeWeight;
}
int main(){
int min;
int edgeCnt=0;
//把邻接矩阵转换为按边集的方式存储
for(int i = 0 ; i < VERTEXT_NUMBER ; i++ ){
for(int j = 0 ; j < VERTEXT_NUMBER ; j++){
if( graph[i][j] != 0 && INFINITY != graph[i][j] ){
graEdge[edgeCnt].begin = i ;
graEdge[edgeCnt].end = j ;
graEdge[edgeCnt].weight = graph[i][j] ;
edgeCnt++;
}
}
}
quicksort(graEdge,0,edgeCnt-1);
min = Kruskal();
for(int i = 0; i< (VERTEXT_NUMBER-1) ;i++){
printf("begin:%d,end:%d,weight:%d\n",treeEdge[i].begin,treeEdge[i].end,treeEdge[i].weight);
}
printf("min:%d\n",min);
return 0;
}
上图便是代码中所用到的测试样例，左边为图，右边为该图生成的最小生成树。
代码完成了，测试样例也通过了，便可以用POJ的题来测试代码是否考虑周到。POJ2485题是一道很简单的题，也是一道挺贴合实际的题，同时也是一道关于最小生成树的经典题。
我不把题目贴上来了，因为如果把题目和题解放在一起，很多人遇到一点想不通的地方便会忍不住瞧两眼题解。这样就不利于对克鲁斯卡尔算法的学习。所以我就把原题的链接放上来，大家都可以去做一下，巩固一下克鲁斯卡尔算法的知识。
原题的链接为：http://poj.org/problem?id=2485
#include
#define INFINITY 655350
#define MAX_VERTEXT_NUMBER 600
//要用到并查集的知识，因为要查找两个节点是否在同一科书中
typedef struct edge{
int begin;
int end;
int weight;
}Edge;
int graph[MAX_VERTEXT_NUMBER][MAX_VERTEXT_NUMBER];
Edge graEdge[ (MAX_VERTEXT_NUMBER * MAX_VERTEXT_NUMBER)];
Edge treeEdge[MAX_VERTEXT_NUMBER];
int preNode[MAX_VERTEXT_NUMBER];
int nodeNum;
//记录边的数目
int edgeCnt;
/** void quicksort(long *arr,int start,int last)
*\brief 快速排序，在原数组的基础上进行排序
*
* \param start：进行排序的数组的起点下标
* \param last：进行排序的数组的终点下标,排序数组包含该下标的元素
* \return 无
*
*/
void quicksort(Edge *arr,int start,int last){
if(start>=last){
return ;
}
int left=start,right=last,pos=start+1;
Edge tmp,pivotValue=arr[start];
while(left!=right){
if(arr[pos].weight>pivotValue.weight){
//由于两个数进行了交换，pos位置的值是新值，所以不用后移
tmp=arr[right];
arr[right--]=arr[pos];
arr[pos]=tmp;
}else{
arr[left++]=arr[pos];
pos++;
}
}
arr[left]=pivotValue;
quicksort(arr,start,left-1);
quicksort(arr,left+1,last);
}
//查找并查集中的祖先元素
int find(int nodeA){
int anceA=preNode[nodeA],tmp;
//如果他不是根节点，循环，直至找到根节点
while(anceA != preNode[anceA]){
anceA = preNode[anceA];
}
//压缩并查集，让一课集合内的节点都指向一个根（代表元素）
while(anceA != preNode[nodeA]){
tmp = preNode[nodeA];
preNode[nodeA] = anceA;
nodeA = tmp;
}
return anceA;
}
//合并两个集合的根节点（代表元素）
void merge(int unionA,int unionB){
preNode[unionB] = unionA;
}
int Kruskal(){
int edgeMaxWeight = 0;
int edgeCnt=0; //记录已遍历多少条边
int treeEdgeCnt = 0;
int beParent,endParent;
for(int i= 0 ; i < nodeNum ;i++){
//初始化并查集
preNode[i] = i;
}
//最小生成树有n-1条边，n为节点数
while( treeEdgeCnt < (nodeNum-1)){
if( (beParent = find(graEdge[edgeCnt].begin)) != (endParent = find(graEdge[edgeCnt].end)) ){
treeEdge[treeEdgeCnt] = graEdge[edgeCnt];
treeEdgeCnt++;
if( graEdge[edgeCnt].weight > edgeMaxWeight){
edgeMaxWeight = graEdge[edgeCnt].weight ;
}
merge(beParent,endParent);
}
edgeCnt++;
}
return edgeMaxWeight;
}
void ChangeToEdge(){
edgeCnt = 0;
for(int i = 0 ; i < nodeNum ; i++ ){
for(int j = 0 ; j < nodeNum ; j++){
if( graph[i][j] != 0 && INFINITY != graph[i][j] ){
graEdge[edgeCnt].begin = i ;
graEdge[edgeCnt].end = j ;
graEdge[edgeCnt].weight = graph[i][j] ;
edgeCnt++;
}
}
}
}
int main(){
int maxedge;
int t,i,j,k;
scanf("%d",&t);
for( i =0; i < t ; i++){
scanf("%d",&nodeNum);
for( j = 0 ; j < nodeNum ; j++){
for( k = 0 ; k < nodeNum ; k++){
scanf("%d",&graph[j][k]);
}
}
//把邻接矩阵边提取出来
ChangeToEdge();
quicksort(graEdge,0,edgeCnt-1);
maxedge = Kruskal();
printf("%d\n",maxedge);
}
return 0;
}
文章的篇幅有点长，请大家不要介意，因为这些知识是一个体系的。无论把哪一部分单独分出去讲，整个体系的知识就总有一点残缺。
Github传送门：https://github.com/OLPMO/DataStructure_And_Algorithm
这是我在github上面关于数据结构与算法的仓库，里面总结了我所接触过的数据结构和算法的代码，有需要的可以去上面看一下。参考资料：
关于的并查集：
http://www.cnblogs.com/cyjb/p/UnionFindSets.html
克鲁斯卡尔算法的维基百科：
https://en.wikipedia.org/wiki/Kruskal%27s_algorithm
克鲁斯卡尔算法的百度百科：
http://baike.baidu.com/link?url=rjz-99kfuiX_d0dpqak__oqZRtq-mIDbWuqxB6n1kwH8DCzOZJP1T4ayL1v3Mie0
POJ2485题：
http://poj.org/problem?id=2485