Prim算法和Kruskal算法

骑猪看日落 2022-07-12 08:52 187阅读 0赞

### 原文地址: ###

### http://blog.csdn.net/believejava/article/details/17414037 ###

http://www.cnblogs.com/biyeymyhjob/archive/2012/07/30/2615542.html

### Prim算法和Kruskal算法都能从连通图找出最小生成树。区别在于Prim算法是挨个找，而Kruskal是先排序再找。 ###

一、Prim[算法][Link 1]：

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

Prim算法是这样来做的：

首先以一个结点作为最小生成树的初始结点，然后以迭代的方式找出与最小生成树中各结点权重最小边，并加入到最小生成树中。加入之后如果产生回路则跳过这条边，选择下一个结点。当所有结点都加入到最小生成树中之后，就找出了连通图中的最小生成树了。

Prim算法最小生成树查找过程：

![81eaa7e5-492e-3cc4-bdc4-062ae70f8a1e.jpg][]

C语言实现：

#include <stdio.h>  
        　　#include <stdlib.h>  
        　　#define maxint 1073741824  
        　　int main()  
        　　{  
        　　FILE *input=fopen("input.txt","r"),*out=fopen("output.txt","w");  
        　　int n,m,i,j,x,y,w;  
        　　fscanf(input,"%d %d",&n,&m);  
        　　int map[n][n],E[m][3],tree[m],Mst[n][n];  
        　　/*Mst表示最小生成树的邻接矩阵，map是原图，E是边集，其中E[0]和E[1]是边的两个顶点，E[2]是边的权值，tree是用于判断原图的点是否在最小生成树中*/  
        　　memset(tree,0,sizeof(tree));  
        　　for(i=0; i<n; i++)  
        　　{  
        　　for(j=0; j<n; j++)  
        　　{  
        　　map[i][j]=maxint;  
        　　Mst[i][j]=maxint;  
        　　}  
        　　E[i][0]=E[i][1]=maxint;  
        　　}  
        　　for(i=0; i<m; i++)  
        　　{  
        　　fscanf(input,"%d %d %d",&x,&y,&w);  
        　　if(w<map[x][y])  
        　　{  
        　　map[x][y]=w;  
        　　map[y][x]=w;  
        　　}  
        　　}  
        　　int min=maxint,next=0,now=0,k=0;  
        　　tree[0]=1;  
        　　for(i=0; i<n; i++)  
        　　{  
        　　for(j=0; j<n; j++)  
        　　{  
        　　if(map[now][j]!=maxint && tree[j]==0)  
        　　{  
        　　E[k][0]=now;  
        　　E[k][2]=map[now][j];  
        　　E[k++][1]=j;  
        　　}  
        　　}  
        　　for(j=0; j<k; j++)  
        　　{  
        　　if(E[j][2]<min && tree[E[j][1]]==0)  
        　　{  
        　　min=E[j][2];  
        　　x=E[j][0];  
        　　y=E[j][1];  
        　　next=y;  
        　　}  
        　　}  
        　　tree[next]=1;  
        　　now=next;  
        　　Mst[x][y]=map[x][y];  
        　　Mst[y][x]=map[y][x];  
        　　min=maxint;  
        　　}  
        　　for(i=0; i<n; i++)  
        　　{  
        　　for(j=0; j<n; j++)  
        　　{  
        　　if(Mst[i][j]==maxint) //判断两点是否连通  
        　　fprintf(out,"00 "); //美化输出，不必多加探究  
        　　else  
        　　{  
        　　fprintf(out,"%d ",Mst[i][j]); //输出生成树的邻接矩阵，要输出树的自己可以根据邻接矩阵的数据进行加工  
        　　}  
        　　}  
        　　fprintf(out,"\n");  
        　　}  
        　　fclose(input);  
        　　fclose(out);  
        　　return 0;  
        　　} // 程序未考虑不是连通图的情况，修改很简单，判断生成树的节点数量是否等于原图的节点数量  
        　　//如果小于（不会有大于）则本图不是连通图  
        　　//其实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)。与图中边数无关，该算法适合于稠密图。

算法演示：

http://sjjp.tjuci.edu.cn/sjjg/DataStructure/DS/web/flashhtml/prim.htm

二、Kruskal算法：

**1.概览**

**Kruskal算法**是一种用来寻找最小生成树的算法，由Joseph Kruskal在1956年发表。用来解决同样问题的还有Prim算法和Boruvka算法等。三种算法都是贪婪算法的应用。和Boruvka算法不同的地方是，Kruskal算法在图中存在相同权值的边时也有效。

**2.算法简单描述**

1).记Graph中有v个顶点，e个边

2).新建图Graphnew，Graphnew中拥有原图中相同的e个顶点，但没有边

3).将原图Graph中所有e个边按权值从小到大排序

4).循环：从权值最小的边开始遍历每条边 直至图Graph中所有的节点都在同一个连通分量中

if 这条边连接的两个节点于图Graphnew中不在同一个连通分量中

添加这条边到图Graphnew中

图例描述：

![2012073015215729.jpg][]首先第一步，我们有一张图Graph，有若干点和边

![2012073015234045.jpg][]

将所有的边的长度排序，用排序的结果作为我们选择边的依据。这里再次体现了贪心算法的思想。资源排序，对局部最优的资源进行选择，排序完成后，我们率先选择了边AD。这样我们的图就变成了右图

![2012073015313195.jpg][]在剩下的变中寻找。我们找到了CE。这里边的权重也是5

![2012073015332154.jpg][]依次类推我们找到了6,7,7，即DF，AB，BE。

![2012073015361536.jpg][]

下面继续选择， BC或者EF尽管现在长度为8的边是最小的未选择的边。但是现在他们已经连通了（对于BC可以通过CE,EB来连接，类似的EF可以通过EB,BA,AD,DF来接连）。所以不需要选择他们。类似的BD也已经连通了（这里上图的连通线用红色表示了）。

最后就剩下EG和FG了。当然我们选择了EG。最后成功的图就是右：

**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'的生成树。所以W(T-\{<u,v>\})<=W(T')，也就是W(T)<=W(T')+W(<u,v>)=W(T'+\{<u,v>\})，产生了矛盾。于是假设不成立，T'+\{<u,v>\}是G的最小生成树，Kruskal算法对k+1阶图也适用。

由数学归纳法，Kruskal算法得证。

#include "stdio.h"  
    　　#define maxver 10  
    　　#define maxright 100  
    　　int 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;  
    　　}  
    　　else  
    　　if(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;  
    　　}  
    　　else  
    　　if(pre!=i)  
    　　FindCircle(start,i,times,begin);  
    　　else  
    　　continue;  
    　　}  
    　　return 1;  
    　　}

算法描述：克鲁斯卡尔算法需要对图的边进行访问，所以克鲁斯卡尔算法的时间复杂度只和边又关系，可以证明其时间复杂度为O（eloge）。

算法过程：

1.将图各边按照权值进行排序

2.将图遍历一次，找出权值最小的边，（条件：此次找出的边不能和已加入最小生成树集合的边构成环），若符合条件，则加入最小生成树的集合中。不符合条件则继续遍历图，寻找下一个最小权值的边。

3.递归重复步骤1，直到找出n-1条边为止（设图有n个结点，则最小生成树的边数应为n-1条），算法结束。得到的就是此图的最小生成树。

克鲁斯卡尔（Kruskal）算法因为只与边相关，则适合求稀疏图的最小生成树。而prime算法因为只与顶点有关，所以适合求稠密图的最小生成树。

无疑，Kruskal算法在效率上要比Prim算法快，因为Kruskal只需要对权重边做一次排序，而Prim算法则需要做多次排序。尽管Prim算法每次做的算法涉及的权重边不一定会涵盖连通图中的所有边，但是随着所使用的排序算法的效率的提高，Kruskal算法和Prim算法之间的差异将会清晰的显性出来。

[Link 1]: http://lib.csdn.net/base/datastructure
[81eaa7e5-492e-3cc4-bdc4-062ae70f8a1e.jpg]: /images/20220710/510be28faeb241268613cac848729e70.png
[2012073015215729.jpg]: /images/20220710/5ab7850522924a439e75427bfb139972.png
[2012073015234045.jpg]: /images/20220710/6424b479e0164b5fa45d28ffbfa3c66c.png
[2012073015313195.jpg]: /images/20220710/4635a66036004737a35daac1ae11881b.png
[2012073015332154.jpg]: /images/20220710/c3ce6a2db3a04432a24d319ca9d44d23.png
[2012073015361536.jpg]: /images/20220710/f503e9c2d7aa4cedb5a300c1cf84ef92.png