最小生成树(Kruskal算法)

Kruskal算法和Prim算法本节所阐述的两种最小生成树算法是上节所介绍的一般算法的细化。

每个算法均采用一特定规则来确定GENERIC-MST算法第3行所描述的安全边；在Kruskal算法中，集合A是一森林，加大集合A中的安全边总是图中连结两不同连通支的最小权边。

在Prim算法中，集合A仅形成单棵树。

添加入集合A的安全边总是连结树与一非树结点的最小权边。

Kruskal算法Kruskal算法是直接基于上一节中给出的一般最小生成树算法的基础之上的。

该算法找出森林中连结任意两棵树的所有边中具有最小权值的边(u,v)作为安全边，并把它添加到正在生长的森林中。

设C1和C2表示边(u,v)连结的两棵树。

因为(u,v)必是连C1和其他某棵树的一条轻边，所以由推论2可知(u,v)对C1是安全边。

Kruskal算法同时也是一种贪心算法，因为算法每一步添加到森林中的边的权值都尽可能小。

Kruskal算法的实现类似于计算连通支的算法。

它使用了分离集合数据结构以保持数个互相分离的元素集合。

每一集合包含当前森林中某个树的结点，操作FIND-SET(u)返回包含u的集合的一个代表元素，因此我们可以通过FIND-SET(v)来确定两结点u和v是否属于同一棵树，通过操作UNION来完成树与树的联结。

MST-KRUSKAL(G,w)1. A←∅2. for 每个结点v V[G]3. do MAKE-SET(v)4. 根据权w的非递减顺序对E的边进行排序5. for 每条边(u,v)∈E，按权的非递减次序6. do if FIND-SET(u) ≠ FIND-SET(v)7. then A←A∪{(u,v)}8. UNION(u,v)9 return AKruskal算法的工作流程如图4所示。

阴影覆盖的边属于正在生成的森林A。

算法按权的大小顺序考察各边。

箭头指向算法每一步所考察到的边。

第1-3行初始化集合A为空集并建立|V|棵树，每裸树包含图的一个结点。

最小生成树的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算法是一种用于求解最小生成树的算法，它的主要特点是按边的权值大小进行排序，并逐步添加边，直到构成一棵生成树为止。

在实际应用中，Kruskal算法通常被用来解决各种最小生成树的问题，比如公路修建、通信网络的建设、电路板的设计等等。

本文将着重介绍Kruskal算法的原理、步骤和具体应用，以期为读者提供全面的了解和指导。

一、Kruskal算法的原理Kruskal算法是一种基于贪心策略的算法，它通过不断地选择边来构建生成树，直到所有的顶点都被包含在生成树中。

其基本原理可以概括如下：1. 将图中的所有边按权值大小进行排序。

2. 依次从小到大选择边，并检查是否形成环路。

3. 如果没有形成环路，则将该边添加到生成树中。

Kruskal算法的核心思想是“先小后大”，即先选择权值较小的边，直到所有的顶点都被包含在生成树中。

由于Kruskal算法是基于边来构建生成树的，因此它适用于稀疏图和稠密图，而且在实际应用中通常具有较好的效率。

二、Kruskal算法的步骤Kruskal算法的具体步骤可以简单总结为以下几个步骤：1. 初始化：将图中的所有边按权值大小进行排序。

2. 创建一个空的数组T来存储最小生成树的边。

3. 依次从排序后的边集合中选择边e，并检查是否添加e会形成环路。

4. 如果不形成环路，则将边e添加到数组T中。

5. 直到T中包含了n-1条边为止，其中n为顶点的个数。

三、Kruskal算法的具体实现下面我们通过一个简单的示例来说明Kruskal算法的具体实现步骤。

示例：假设有如下的图G和边集合E：顶点集合V：{A, B, C, D, E, F, G, H}边集合E：{(A, B, 4), (A, H, 8), (B, C, 8), (B, H, 11), (C, D, 7), (C, F, 4), (C, I, 2), (D, E, 9), (D, F, 14), (E, F, 10), (F, G, 2), (G, H, 1), (G, I, 6), (H, I, 7)}我们可以按照如下的步骤来求解最小生成树：1. 首先对边集合E进行按权值的排序：(E, F, 2), (G, H, 1), (C, I, 2), (A, B, 4), (C, F, 4), (H, I, 7), (C, D, 7), (D, E, 9), (A, H, 8), (B, C, 8), (G, I, 6), (B, H, 11), (D, F, 14)2. 初始化一个空的数组T来存储最小生成树的边，初始化一个数组parent来记录每个顶点的父节点。

最⼩⽣成树---普⾥姆算法（Prim算法）和克鲁斯卡尔算法（Kruskal算法）最⼩⽣成树的性质：MST性质（假设N=(V,{E})是⼀个连通⽹，U是顶点集V的⼀个⾮空⼦集，如果（u，v）是⼀条具有最⼩权值的边，其中u属于U，v属于V-U，则必定存在⼀颗包含边（u，v）的最⼩⽣成树）普⾥姆算法（Prim算法)思路：以点为⽬标构建最⼩⽣成树1.将初始点顶点u加⼊U中，初始化集合V-U中各顶点到初始顶点u的权值；2.根据最⼩⽣成树的定义：从n个顶点中，找出 n - 1条连线，使得各边权值最⼩。

循环n-1次如下操作：（1）从数组lowcost[k]中找到vk到集合U的最⼩权值边，并从数组arjvex[k] = j中找到该边在集合U中的顶点下标(2)打印此边，并将vk加⼊U中。

（3）通过查找邻接矩阵Vk⾏的各个权值，即vk点到V-U中各顶点的权值，与lowcost的对应值进⾏⽐较，若更⼩则更新lowcost，并将k存⼊arjvex数组中以下图为例#include<bits/stdc++.h>using namespace std;#define MAXVEX 100#define INF 65535typedef char VertexType;typedef int EdgeType;typedef struct {VertexType vexs[MAXVEX];EdgeType arc[MAXVEX][MAXVEX];int numVertexes, numEdges;}MGraph;void CreateMGraph(MGraph *G) {int m, n, w; //vm-vn的权重wscanf("%d %d", &G->numVertexes, &G->numEdges);for(int i = 0; i < G->numVertexes; i++) {getchar();scanf("%c", &G->vexs[i]);}for(int i = 0; i < G->numVertexes; i++) {for(int j = 0; j < G->numVertexes; j++) {if(i == j) G->arc[i][j] = 0;else G->arc[i][j] = INF;}}for(int k = 0; k < G->numEdges; k++) {scanf("%d %d %d", &m, &n, &w);G->arc[m][n] = w;G->arc[n][m] = G->arc[m][n];}}void MiniSpanTree_Prim(MGraph G) {int min, j, k;int arjvex[MAXVEX]; //最⼩边在 U集合中的那个顶点的下标int lowcost[MAXVEX]; // 最⼩边上的权值//初始化,从点 V0开始找最⼩⽣成树Tarjvex[0] = 0; //arjvex[i] = j表⽰ V-U中集合中的 Vi点的最⼩边在U集合中的点为 Vjlowcost[0] = 0; //lowcost[i] = 0表⽰将点Vi纳⼊集合 U ，lowcost[i] = w表⽰ V-U中 Vi点到 U的最⼩权值for(int i = 1; i < G.numVertexes; i++) {lowcost[i] = G.arc[0][i];arjvex[i] = 0;}//根据最⼩⽣成树的定义：从n个顶点中，找出 n - 1条连线，使得各边权值最⼩for(int i = 1; i < G.numVertexes; i++) {min = INF, j = 1, k = 0;//寻找 V-U到 U的最⼩权值minfor(j; j < G.numVertexes; j++) {// lowcost[j] != 0保证顶点在 V-U中，⽤k记录此时的最⼩权值边在 V-U中顶点的下标if(lowcost[j] != 0 && lowcost[j] < min) {min = lowcost[j];k = j;}}}printf("V[%d]-V[%d] weight = %d\n", arjvex[k], k, min);lowcost[k] = 0; //表⽰将Vk纳⼊ U//查找邻接矩阵Vk⾏的各个权值，与lowcost的对应值进⾏⽐较，若更⼩则更新lowcost，并将k存⼊arjvex数组中for(int i = 1; i < G.numVertexes; i++) {if(lowcost[i] != 0 && G.arc[k][i] < lowcost[i]) {lowcost[i] = G.arc[k][i];arjvex[i] = k;}}}int main() {MGraph *G = (MGraph *)malloc(sizeof(MGraph));CreateMGraph(G);MiniSpanTree_Prim(*G);}/*input:4 5abcd0 1 20 2 20 3 71 2 42 3 8output:V[0]-V[1] weight = 2V[0]-V[2] weight = 2V[0]-V[3] weight = 7最⼩总权值: 11*/时间复杂度O(n^2)克鲁斯卡尔算法（Kruskal算法）思路：以边为⽬标进⾏构建最⼩⽣成树在边集中依次寻找最⼩权值边，若构建是不形成环路（利⽤parent数组记录各点的连通分量），则将其添加到最⼩⽣成树中。

用Kruskal算法求无向图的最小生成树该图用邻接矩阵表示，邻接表原理与之相同。

可以指出的是，对于有向图，算法可以做得更加简单，因为对无向图的“回边”情况的处理比有向图回边情况的处理要复杂一些。

图1：输入示例图二：输入时若两点之间没有公共边，则将权值设置为-1。

程序设置处理的最大点数为10。

图三：注意到Kruskal算法的解答结果有时候不是唯一的，这个结果和对图遍历时的顺序有关，但是必需注意的是所有的最小生成树其网络代价和是一样的。

下面是源代码：/* 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[i][0]=v1;path[i][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[i][0]+1,path[i][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][i]==1){if(i==start&&pre!=start){circle=1;return 1;break;}elseif(pre!=i)FindCircle(start,i,times,begin); elsecontinue;}return 1;}。

Kruskal 算法及其应用Kruskal 算法是一种求解最小生成树的算法，其思想是将边按照权值从小到大排序，然后依次将边加入到已构建的生成树中，直到生成树中的边数等于顶点数减一。

Kruskal 算法具有良好的时间复杂度和空间复杂度，因此在实际应用中得到广泛的应用。

本文将介绍 Kruskal 算法的基本思想、证明方法以及其在实际应用中的应用。

下面是本店铺为大家精心编写的4篇《Kruskal 算法及其应用》，供大家借鉴与参考，希望对大家有所帮助。

《Kruskal 算法及其应用》篇1一、Kruskal 算法的基本思想Kruskal 算法是一种求解最小生成树的算法，其基本思想是将边按照权值从小到大排序，然后依次将边加入到已构建的生成树中，直到生成树中的边数等于顶点数减一。

Kruskal 算法的时间复杂度为O(ElogE)，其中 E 表示边的数量。

Kruskal 算法的实现过程可以分为三个步骤：1. 将所有边按照权值从小到大排序；2. 初始化一个空的生成树；3. 依次将排序后的边加入到生成树中，直到生成树中的边数等于顶点数减一。

二、Kruskal 算法的证明方法Kruskal 算法的正确性可以通过证明生成的生成树是最小生成树来证明。

具体来说，可以采用贪心算法的思路，证明 Kruskal 算法得到的生成树是局部最优的，即每次加入的边都是当前状态下的最小边。

证明过程可以分为以下几个步骤：1. 证明 Kruskal 算法得到的生成树是连通的；2. 证明 Kruskal 算法得到的生成树是树结构；3. 证明 Kruskal 算法得到的生成树是最小生成树。

三、Kruskal 算法在实际应用中的应用Kruskal 算法在实际应用中得到广泛的应用，如下：1. 最小生成树：Kruskal 算法可以用于求解最小生成树，将其应用于网络设计、图像处理、生物信息学等领域。

2. 单源最短路径：Kruskal 算法可以用于求解单源最短路径，将其应用于路由算法、图像处理、生物信息学等领域。

Prim算法和Kruskal算法Prim算法和Kruskal算法都能从连通图找出最小生成树。

区别在于Prim算法是挨个找，而Kruskal是先排序再找。

一、Prim算法：Prim算法实现的是找出一个有权重连通图中的最小生成树，即：具有最小权重且连接到所有结点的树。

(强调的是树，树是没有回路的)。

Prim算法是这样来做的：首先以一个结点作为最小生成树的初始结点，然后以迭代的方式找出与最小生成树中各结点权重最小边，并加入到最小生成树中。

加入之后如果产生回路则跳过这条边，选择下一个结点。

当所有结点都加入到最小生成树中之后，就找出了连通图中的最小生成树了。

Prim算法最小生成树查找过程：注意：若候选轻边集中的轻边不止一条，可任选其中的一条扩充到T中。

连通网的最小生成树不一定是惟一的，但它们的权相等。

【例】在上图(e)中，若选取的轻边是(2，4)而不是(2，1)时，则得到如图(h)所示的另一棵MST。

算法特点该算法的特点是当前形成的集合T始终是一棵树。

将T中U和TE分别看作红点和红边集，V-U看作蓝点集。

算法的每一步均是在连接红、蓝点集的紫边中选择一条轻边扩充进T中。

MST性质保证了此边是安全的。

T从任意的根r开始，并逐渐生长直至U=V，即T 包含了C中所有的顶点为止。

MST性质确保此时的T是G的一棵MST。

因为每次添加的边是使树中的权尽可能小，因此这是一种"贪心"的策略。

算法分析该算法的时间复杂度为O(n2)。

与图中边数无关，该算法适合于稠密图。

算法演示：/sjjg/DataStructure/DS/web/flashhtml/prim.htm二、Kruskal算法：Kruskal算法与Prim算法的不同之处在于，Kruskal在找最小生成树结点之前，需要对所有权重边做从小到大排序。

将排序好的权重边依次加入到最小生成树中，如果加入时产生回路就跳过这条边，加入下一条边。

当所有结点都加入到最小生成树中之后，就找出了最小生成树。

克鲁斯卡尔（Kruskal）算法从另一途径求网的最小生成树。

其基本思想是：假设连通网G=（V，E），令最小生成树的初始状态为只有n个顶点而无边的非连通图T=（V，{}），概述图中每个顶点自成一个连通分量。

在E中选择代价最小的边，若该边依附的顶点分别在T 中不同的连通分量上，则将此边加入到T中；否则，舍去此边而选择下一条代价最小的边。

依此类推，直至T中所有顶点构成一个连通分量为止
克鲁斯卡尔算法思想设计克鲁斯卡尔算法函数主要包括两个部分：首先是带权图G中e条边的权值的排序；其次是判断新选取的边的两个顶点是否属于同一个连通分量。

对带权图G中e条边的权值的排序方法可以有很多种，各自的时间复杂度均不相同，对e条边的权值排序算法时间复杂度较好的算法有快速排序法、堆排序法等，这些排序算法的时间复杂度均可以达到O（elge）。

判断新选取的边的两个顶点是否属于同一个连通分量的问题是一个在最多有n个顶点的生成树中遍历寻找新选取的边的两个顶点是否存在的问题，此算法的时间复杂度最坏情况下为O（n）。