Kruskal算法说明及图解

Kruskal算法的思想、证明及步骤Kruskal算法思想：把n个顶点看成看成n棵分离的树（每棵树只有⼀个顶点），每次选取可连接两个分离树中权值最⼩的边把两个分离的树合成⼀个新的树取代原来的两个分离树，如果重复n-1步后便得到最⼩⽣成树。

Kruskal算法步骤：T0存放⽣成树的边，初值为空C(T0) 最⼩⽣成树的权，初值为0VS 分离树顶点的集合，初值为 { {v1} {v2} … {v n} }A B W分别为边的顶点和权值数组，由⽤户输⼊1) T0←0, C(T0)←0, VS←{ {v1} {v2} … {v n} }, A, B, W按W排序后构成队列Q2) If n(VS)==1 then stop else goto 33) 取Q第⼀组数组(u, v, w) 并从Q中将其删除.4) If u, v 属于同⼀个集合 then goto 3 else 分属两个集合X, Y, goto 5.5) T0←T0∪(u, v), C(T0)←C(T0)+w, VS←VS-X-Y+X∪Y goto 2.Kruskal算法证明：树定义：⽆圈连通图。

引理1：⼀个图是树等价于⼀个图⽆圈且任意不相关联的顶点u, v ，图G+(u, v)则必存在唯⼀⼀个圈。

设由Kruskal算法⽣成的T0序列为e1, e2, e3 … e v-1，假设其不是最⼩⽣成树。

任意最⼩⽣成树T定义函数f(T)：T0中不存在于T中边在T0的下标。

设T1是使f(T)最⼤的变量，设f(T1)=k，即e k不存在于T1中，T1为树且e k不在T1中，所以由引理1得T1+e k必存在圈C，C上必有e,k ≠e k，e,k不在T0中。

现令T2 = T1 - e,k + e k，则T2也为⽣成树但由Kruskal算法可知e k是使e1, e2 … e k-1, e k⽆圈的权值最⼩的边，e1, e2 … e k-1, e ,k是树的⼦图必⽆圈故e,k的权值必定⼩于e k，即T2的总权值不⼤于T1的权值，因T1是最⼩⽣成树，故必T2也是最⼩⽣成树，但f(T2)＞k与k是f函数最⼤取值⽭盾，故T0是最⼩⽣成树。

最小生成树的Kruskal算法Kruskal算法基本思想：每次选不属于同一连通分量(保证不生成圈)且边权值最小的顶点，将边加入MST，并将所在的2个连通分量合并，直到只剩一个连通分量排序使用Quicksort(O(eloge))检查是否在同一连通分量用Union-Find，每次Find和union运算近似常数Union-Find使用rank启发式合并和路径压缩总复杂度O(eloge)=O(elogv) (因为e<n(n-1)/2)}constmaxn=100;maxe=maxn*maxn;typeedge=recorda,b :integer; //边的2个顶点len :integer; //边的长度end;varedges :array[0..maxe]of edge; //保存所有边的信息p,r :array[0..maxn]of integer; //p保存i的父亲节点，r用来实现Union-Find的rank启发式n,e :integer; //n为顶点数，e为边数procedure swap(a,b:integer); //交换beginedges[0]:=edges[a];edges[a]:=edges[b];edges[b]:=edges[0];end;procedure quicksort(l,r:integer); //快速排序varx,i,j :integer;beginx:=edges[random(r-l+1)+l].len;i:=l;j:=r;repeatwhile edges[i].len<x do inc(i);while edges[j].len>x do dec(j);if i<=j thenbeginswap(i,j);inc(i);dec(j);enduntil i>j;if l<j then quicksort(l,j);if i<r then quicksort(i,r);end;procedure init;vari :integer;beginassign(input,'g.in');reset(input);readln(n,e);for i:=1 to e do readln(edges[i].a,edges[i].b,edges[i].len); //从文件读入图的信息for i:=1 to n do p[i]:=i; //初始化并查集randomize;quicksort(1,e); //使用快速排序将边按权值从小到大排列end;function find(x:integer):integer; //并查集的Find，用来判断2个顶点是否属于一个连通分量beginif x<>p[x] then p[x]:=find(p[x]);find:=p[x]end;procedure union(a,b:integer); //如果不属于且权值最小则将2个顶点合并到一个连通分量vart :integer;begina:=find(a);b:=find(b);if r[a]>r[b] then begin t:=a;a:=b;b:=t end;if r[a]=r[b]then inc(r[a]);p[a]:=b;end;procedure kruskal; //主过程varen :integer; //en为当前边的编号count :integer; //统计进行了几次合并。

贪心策略是指从问题的初始状态出发，通过若干次的贪心选择而得出最优值(或较优解)的一种解题方法。

Ⅰ、库鲁斯卡尔（Kruskal）算法【定义4】设图G=（V，E）是一简单连通图，｜V｜ =n,｜E｜=m,每条边ei都给以权W ，W 假定是边e 的长度（其他的也可以），i=1，2，3，...，m。

求图G的总长度最短的树，这就是最短树问题。

kruskal算法的基本思想是：首先将赋权图G的边按权的升序排列，不失一般性为：e ,e ,......,e 。

其中W ≤W ，然后在不构成回路的条件下择优取进权最小的边。

其流程如下：（1）对属于E的边进行排序得e ≤e ≤...... ≤e 。

（2）初始化操作 w←0，T←ф，k←0，t←0；（3）若t=n-1，则转（6），否则转（4）（4）若T∪｛e ｝构成一回路，则作【k←k+1，转（4）】（5） T←T∪{ e }，w←w+ w ，t←t+1，k←k+1，转（3）（6）输出T，w，停止。

下面我们对这个算法的合理性进行证明。

设在最短树中，有边〈v ，v 〉，连接两顶点v ，v ，边〈v ，v 〉的权为wp，若〈v ，v 〉加入到树中不能保证树的总长度最短，那么一定有另一条边〈v ，v 〉或另两条边〈v ，v 〉、〈v ，v 〉，且w<vi，vj><wp或w<vi，vk>+w〈vk，vj〉<wp，因为〈v ，v 〉、〈v ，v 〉不在最短树中，可知当〈v ，v 〉、〈v ，v 〉加入到树中时已构成回路，此时程序终止。

因为〈v ，v 〉∈ T，〈v ，v 〉∈T且w〈vI，vk〉+w〈vk，vj〉<w p，与程序流程矛盾。

普林（Prim）算法：Kruskal算法采取在不构成回路的条件下，优先选择长度最短的边作为最短树的边，而Prim则是采取了另一种贪心策略。

已知图G=（V，E），V={v ，v ，v ，...， v }，D=（d ）是图G的矩阵，若〈v ，v 〉∈E，则令dij=∞，并假定dij=∞Prim算法的基本思想是：从某一顶点（设为v ）开始，令S←｛v ｝，求V/S中点与S中点v 距离最短的点，即从矩阵D的第一行元素中找到最小的元素，设为d ，则令S ←S∪ { v }，继续求V/S中点与S的距离最短的点，设为v ,则令S←S∪{ v }，继续以上的步骤，直到n个顶点用n-1条边连接起来为止。

kruskal算法百科名片K r u s k a l算法每次选择n- 1条边，所使用的贪婪准则是：从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合中。

注意到所选取的边若产生环路则不可能形成一棵生成树。

K r u s k a l算法分e 步，其中e 是网络中边的数目。

按耗费递增的顺序来考虑这e 条边，每次考虑一条边。

当考虑某条边时，若将其加入到已选边的集合中会出现环路，则将其抛弃，否则，将它选入。

目录[隐藏]Kruskal算法普里姆算法（prim算法）Kruskal算法普里姆算法（prim算法）[编辑本段]Kruskal算法算法定义克鲁斯卡尔算法假设WN=(V,{E}) 是一个含有n 个顶点的连通网，则按照克鲁斯卡尔算法构造最小生成树的过程为：先构造一个只含n 个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它是一个含有n 棵树的一个森林。

之后，从网的边集 E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。

依次类推，直至森林中只有一棵树，也即子图中含有n-1条边为止。

举例描述初始时没有任何边被选择。

边（ 1 , 6）是最先选入的边，它被加入到欲构建的生成树中，得到图1 3 - 1 2 c。

下一步选择边（3，4）并将其加入树中（如图1 3 - 1 2 d所示）。

然后考虑边( 2，7 ，将它加入树中并不会产生环路，于是便得到图1 3 - 1 2 e。

下一步考虑边（2，3）并将其加入树中（如图1 3 - 1 2 f所示）。

在其余还未考虑的边中，（7，4）具有最小耗费，因此先考虑它，将它加入正在创建的树中会产生环路，所以将其丢弃。

此后将边（5，4）加入树中，得到的树如图13-12g 所示。

下一步考虑边（7，5），由于会产生环路，将其丢弃。

1. Kruskal算法(1) 算法思想K r u s k a l算法每次选择n- 1条边，所使用的贪婪准则是：从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合中。

注意到所选取的边若产生环路则不可能形成一棵生成树。

K r u s k a l算法分e 步，其中e 是网络中边的数目。

按耗费递增的顺序来考虑这e 条边，每次考虑一条边。

当考虑某条边时，若将其加入到已选边的集合中会出现环路，则将其抛弃，否则，将它选入。

初始时没有任何边被选择。

边（ 1 , 6）是最先选入的边，它被加入到欲构建的生成树中，得到图1 3 - 1 2 c。

下一步选择边（ 3，4）并将其加入树中（如图1 3 - 1 2 d所示）。

然后考虑边( 2，7 ，将它加入树中并不会产生环路，于是便得到图1 3 - 1 2 e。

下一步考虑边（ 2，3）并将其加入树中（如图1 3 - 1 2 f所示）。

在其余还未考虑的边中，（7，4）具有最小耗费，因此先考虑它，将它加入正在创建的树中会产生环路，所以将其丢弃。

此后将边（ 5，4）加入树中，得到的树如图13-12g 所示。

下一步考虑边（ 7，5），由于会产生环路，将其丢弃。

最后考虑边（ 6，5）并将其加入树中，产生了一棵生成树，其耗费为9 9。

图1 - 1 3给出了K r u s k a l算法的伪代码。

(2)C代码/* Kruskal.cCopyright (c) 2002, 2006 by ctu_85All Rights Reserved.*//* I am sorry to say that the situation of unconnected graph is not concerned */#include "stdio.h"#define maxver 10#define maxright 100int G[maxver][maxver],record=0,touched[maxver][maxver];int circle=0;int FindCircle(int,int,int,int);int main(){int path[maxver][2],used[maxver][maxver];int i,j,k,t,min=maxright,exsit=0;int v1,v2,num,temp,status=0;restart:printf("Please enter the number of vertex(s) in the graph:\n"); scanf("%d",&num);if(num>maxver||num<0){printf("Error!Please reinput!\n");goto restart;}for(j=0;j<num;j++)for(k=0;k<num;k++){if(j==k){G[j][k]=maxright;used[j][k]=1;touched[j][k]=0;}elseif(j<k){re:printf("Please input the right between vertex %d and vertex %d,if no edge exists please input -1:\n",j+1,k+1);scanf("%d",&temp);if(temp>=maxright||temp<-1){printf("Invalid input!\n");goto re;}if(temp==-1)temp=maxright;G[j][k]=G[k][j]=temp;used[j][k]=used[k][j]=0;touched[j][k]=touched[k][j]=0;}}for(j=0;j<num;j++){path[j][0]=0;path[j][1]=0;}for(j=0;j<num;j++){status=0;for(k=0;k<num;k++)if(G[j][k]<maxright){status=1;break;}if(status==0)break;}for(i=0;i<num-1&&status;i++){for(j=0;j<num;j++)for(k=0;k<num;k++)if(G[j][k]<min&&!used[j][k]){v1=j;v2=k;min=G[j][k];}if(!used[v1][v2]){used[v1][v2]=1;used[v2][v1]=1;touched[v1][v2]=1;touched[v2][v1]=1;path[0]=v1;path[1]=v2;for(t=0;t<record;t++)FindCircle(path[t][0],path[t][0],num,path[t][0]);if(circle){/*if a circle exsits,roll back*/circle=0;i--;exsit=0;touched[v1][v2]=0;touched[v2][v1]=0;min=maxright;}else{record++;min=maxright;}}}if(!status)printf("We cannot deal with it because the graph is not connected!\n"); else{for(i=0;i<num-1;i++)printf("Path %d:vertex %d to vertex %d\n",i+1,path[0]+1,path[1]+1); }return 1;}int FindCircle(int start,int begin,int times,int pre){ /* to judge whether a circle is produced*/int i;for(i=0;i<times;i++)if(touched[begin]==1){if(i==start&&pre!=start){circle=1;return 1;break;}elseif(pre!=i)FindCircle(start,i,times,begin);elsecontinue;}return 1;}。

Kruskal 算法构造最小生成树构造赋权图(,,)G V E W =，其中12{,,,}n V v v v = 为顶点集合,其中i v 表示第i 个顶点，12{,,,,}i E e e e = 为边的集合，()ij n n W w ⨯=为邻接矩阵，其中i j i j ij i j v v v v w v v ∈⎧⎪=⎨∞⎪⎩顶点与之间的距离，当（，）E ，与之间没有边时科茹斯克尔（Kruskal ）算法如下： （1）选1e E ∈（E 为边的集合），使得1e 是权重最小的边。

（2）若12,,e i e e …，已选好，则从12{,,e }i E e e -…，中选取1i e +，使得 i ）121{,,e }i e e +…，中无圈，且 ii ）是1i e +是12{,,e }i E e e -…，中权重最小的边。

（3）直到选得1V e - 为止。

(V 是集合V 中元素的个数)例：已知9个村庄之间的两两距离见表5，要架设通讯线路把9个村庄连接起来，求所需要通讯线的最小长度。

表5 10个村庄的两两距离数据（单位：km ）(,,)G V E W =，其中129{,,,}V v v v = 为顶点集合,其中i v 表示第i 个村庄，12{,,,,}i E e e e = 为边的集合，99()ij W w ⨯=为邻接矩阵，其中i j i j ij i j v v v v w v v ∈⎧⎪=⎨∞⎪⎩村庄与之间的距离，当（，）E ，与之间没有通讯路线时科茹斯克尔（Kruskal ）算法如下： （1）选1e E ∈（E 为边的集合），使得1e 是距离最小的边。

（2）若12,,e i e e …，已选好，则从12{,,e }i E e e -…，中选取1i e +，使得 i ）121{,,e }i e e +…，中无圈，且 ii ）是1i e +是12{,,e }i E e e -…，中距离最小的边。

（3）直到选得8e 为止。

贪心策略是指从问题的初始状态出发，通过若干次的贪心选择而得出最优值(或较优解)的一种解题方法。

Ⅰ、库鲁斯卡尔（Kruskal）算法【定义4】设图G=（V，E）是一简单连通图，｜V｜ =n,｜E｜=m,每条边ei都给以权W ，W 假定是边e 的长度（其他的也可以），i=1，2，3，...，m。

求图G的总长度最短的树，这就是最短树问题。

kruskal算法的基本思想是：首先将赋权图G的边按权的升序排列，不失一般性为：e ,e ,......,e 。

其中W ≤W ，然后在不构成回路的条件下择优取进权最小的边。

其流程如下：（1）对属于E的边进行排序得e ≤e ≤...... ≤e 。

（2）初始化操作 w←0，T←ф，k←0，t←0；（3）若t=n-1，则转（6），否则转（4）（4）若T∪｛e ｝构成一回路，则作【k←k+1，转（4）】（5） T←T∪{ e }，w←w+ w ，t←t+1，k←k+1，转（3）（6）输出T，w，停止。

下面我们对这个算法的合理性进行证明。

设在最短树中，有边〈v ，v 〉，连接两顶点v ，v ，边〈v ，v 〉的权为wp，若〈v ，v 〉加入到树中不能保证树的总长度最短，那么一定有另一条边〈v ，v 〉或另两条边〈v ，v 〉、〈v ，v 〉，且w<vi，vj><wp或w<vi，vk>+w〈vk，vj〉<wp，因为〈v ，v 〉、〈v ，v 〉不在最短树中，可知当〈v ，v 〉、〈v ，v 〉加入到树中时已构成回路，此时程序终止。

因为〈v ，v 〉∈ T，〈v ，v 〉∈T且w〈vI，vk〉+w〈vk，vj〉<w p，与程序流程矛盾。

普林（Prim）算法：Kruskal算法采取在不构成回路的条件下，优先选择长度最短的边作为最短树的边，而Prim则是采取了另一种贪心策略。

已知图G=（V，E），V={v ，v ，v ，...， v }，D=（d ）是图G的矩阵，若〈v ，v 〉∈E，则令dij=∞，并假定dij=∞Prim算法的基本思想是：从某一顶点（设为v ）开始，令S←｛v ｝，求V/S中点与S中点v 距离最短的点，即从矩阵D的第一行元素中找到最小的元素，设为d ，则令S ←S∪ { v }，继续求V/S中点与S的距离最短的点，设为v ,则令S←S∪{ v }，继续以上的步骤，直到n个顶点用n-1条边连接起来为止。

1. 概览Kruskal算法是一种用来寻找最小生成树的算法，由Joseph Kruskal在1956年发表。

用来解决同样问题的还有Prime 算法和Boruvka 算法等。

三种算法都是贪婪算法的应用。

和Boruvka 算法不同的地方是，Kruskal 算法在图中存在相同权值的边时也有效。

2. 算法简单描述1.记Graph 中有v个顶点，e个边2.新建图Graph new，Graph new中拥有原图中相同的e个顶点，但没有边3.将原图Graph new中所有e个边按权值从小到大排序4.循环：从权值最小的边开始遍历每条边直至图Graph new中所有的节点都在同一个连通分量中如果这条边连接的两个节点于图Graph new中不在同一个连通分量中添加这条边到图Graph new中图例描述：3. 简单证明Kruskal算法对图的顶点数n 做归纳，证明Kruskal 算法对任意n 阶图适用。

归纳基础：n = 1，显然能够找到最小生成树。

归纳过程：假设Kruskal 算法对n ≤k 阶图适用，那么，在k + 1 阶图G 中，我们把最短边的两个端点a 和b 做一个合并操作，即把u 与v 合为一个点v'，把原来接在u 和v 的边都接到v' 上去，这样就能够得到一个k阶图G'(u ,v 的合并是k + 1 少一条边)，G' 最小生成树T' 可以用Kruskal 算法得到。

我们证明T' + {<u,v>} 是G 的最小生成树。

用反证法，如果T' + {<u,v>} 不是最小生成树，最小生成树是T，即W(T) < W(T' + {<u,v>})。

显然T 应该包含<u,v>，否则，可以用<u,v> 加入到T 中，形成一个环，删除环上原有的任意一条边，形成一棵更小权值的生成树。

而T - {<u,v>}，是G' 的生成树。