注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Mihooke's blog

IT之恋

 
 
 

日志

 
 

Kruskal算法  

2014-08-01 20:49:19|  分类: 学习录 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

    Kruskal算法是求解最小生成树MST(Minimum Spanning Tree)的,它是按照网中边的权值递增的顺序构造MST的,求解MST的还有Prim算法。Kruskal算法的思想是:无向连通网G=(V,E),令G的最小生成树为T,其初始值为T=(V,{}),开始时,TG中的n顶点构成,这样T中各顶点各自构成一个连通分量。然后,按照边的权值从大到小的顺序,遍历G的各边,若边的顶点分属不同的2个连通分量,则把此边作为MST的一边,存放到T中。若边的顶点属于同一个连通分量,则舍弃,否则存放T中会形成回路,不符合MST了。依次按照这样的步骤进行,直到遍历n-1条边(为什么是n-1条边呢? /*MST中要形成连通图,而不构成回路,那么n个顶点必定要形成n-1条边,但图的MST可能有多个*/ )。


      在这里,我们可以用反证法来证明为什么要从最小值加起。假设图的任意一棵MST都不包括权值最小的边,现在在MST中加入该边,定会构成回路。那么从回路中去掉任意一条比该边权值大的边,会得到一棵权和更小的MST,这和开始的条件相矛盾,因此是不成立的。

拿下图的例子来说吧,下图是利用Kruskal算法实现MST的过程。如图,一开始,图的每个顶点都是一个连通分量,每次加入一条边。

Kruskal算法 - mihooke - mihooke的博客
 
Kruskal算法 - mihooke - mihooke的博客
 

      所以Kruskal算法的关键就在于判断一条边的是否存在于先前的连通图中,或者说加入该边后是否会构成回路。我们可以用一个辅助数组来实现判断,设为arr[n]arr[n]的初始值为arr[i]=i,当判断一条边(Vi,Vj)时,检查arr[i]arr[j]是否相等,若相等,则该边加入必定会构成回路,舍弃;若不相等,则加入该边,并把当前的连通分量和该边的连通分量合并成一个连通分量。举例说一下,上图中,arr[7]={0,1,2,3,4,5,6},当第一条边(V3,V5)进行判断时,arr[3]!=arr[5],那么加入该边,随之把原先V3V5两个连通分量合并为一个连通分量,arr[n]中把arr[5]赋值为和arr[3]一样的值,假如是3,那么arr[7]就变成了{0,1,2,3,4,3,6};紧接着遍历第二条边(V1,V4)arr[1]!=arr[4],那么加入该边,随之把原先V1V4两个连通分量合并为一个连通分量,arr[n]中把arr[4]赋值为和arr[1]一样的值,假如是1,那么arr[7]就变成了{0,1,2,3,1,3,6};接着遍历第三条(V3,V6),arr[3]!=arr[6]那么加入该边,随之把原先V3V6两个连通分量合并为一个连通分量,arr[n]中把arr[6]赋值为和arr[3]一样的值,那么arr[7]就变成了{0,1,2,3,1,3,3}......,按照这样的合并,在最后一次把(V3,V4)加进去之后,所有的连通分量就应该合并为一个。若再加一条边,必然会形成回路。

这个关键问题解决了之后,然后来看具体算法怎么实现的。


#define MaxVertexNum 30

#define MaxEdge 100

/*用一个结构体域去存储图的信息*/

typedef struct 

{ //结点域

   int vertex1,vertex2;

   int weight;

}ENode;

typedef struct 

{

   int vertexNum,edgeNum;

   char vertexs[MaxVertexNum]; //

   ENode edges[MaxVertexNum]; //顶点

}ELGraph;

void kruskal(ELGraph G,ENode T[])

//T[]是生成的MST存放的数组,也就是每加入一条边,便存放到T[]

{

   int i,j,k;

   int s1,s2;

   int f[MaxVertexNum];

   scanf("%d %d",&vertexNum,&edgeNum);

   for(i=0;i<G.vertexNum;i++)

f[i] = i;

   sort(G.edges);

//这是对边的权值进行排序的函数,在此省略,可以用交换排序、选择排序、冒泡排序、快速排序的排序算法实现,很简单

   j=0;k=0;

   while(k<G.vertexNum-1)//选取n-1条边

   {

s1=f[G.edges[j].vertex1];

s2=f[G.edges[j].vertex2];

if(s1!=s2)

{ //产生一条权值最小边

   T[k].vertex1 = G.edges[j].vertex1;

   T[k].vertex2 = G.edges[j].vertex2;

   T[k].weight = G.edges[j].weight;

   k++;

   for(i=0;i<G.vertexNum;i++)

   if(f[i]==s2)

f[i]=s1; //修改加入边后的连通号

}

j++;

   }

}

上述算法的时间复杂度显然和边数、权值排序算法实现有关,若采用快速排序的话,时间复杂度就是O(edgelog2edge)while执行O(edge)f[]数组执行n-1次,那么总的时间复杂度就是O(edge(edgelog2edge+n))


//快速排序算法实现

int quicksout(Sqlist *s,int low,int hign)

{

int key;

S->r[0] = S->r[low];

key = S->r[low].key;

while(low<high)

{

   while(low<high && S->r[high].key>=key)

high--;

   S->r[low]=S->r[high];

   while(low<high && S->r[low].key<=key)

low++;

   S->r[high]=S->r[low];

}

S->r[low]=S->r[0];

return low;

}

  评论这张
 
阅读(60)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017