Kurskal算法生成最小生成树MST

  1. 云栖社区>
  2. 博客>
  3. 正文

Kurskal算法生成最小生成树MST

嗯哼9925 2017-12-19 14:17:00 浏览698
展开阅读全文

1.解析

while循环其实不是只循环V-1次,因为如果找出的边能够形成环的话,这条边并不是我们需要的边,所以本次循环无效。while循环中其实包含了找出最小的功能,这个其实可以通过单独的一个函数来实现。就是按边长度升序来排列。

kruskal算法其实是一个找边的算法,对于一V个顶点的图,必定由V-1条边构成一个最小生成树,那么按边的权值遍历图每一条边。判断如果添加这条选出的当前权最小的边,图中会不会生成一个环,如果生成环,则当前找到的这条边无效,继续找下一条权值最小边。

每找出一条边,相当于图中合并了两个连通部件(初始化是一个顶点算一个连通部件),因此找到V-1条边就相当于是将原来分离的V个连通部件合并成一个更大的连通部件。

在两个连通部件之间添加一条边,会组成一个更大的连通部件,并且不存在环。

2.算法实例

  1. #include<iostream>        
  2. #include<malloc.h>        
  3. #include<queue>      
  4. #include <algorithm>       
  5. #include<stdlib.h>      
  6. #include<functional>    
  7. using namespace std;        
  8.     
  9. #define maxNum 100 //定义邻接举证的最大定点数      
  10. #define maxWeight 1000000 //边权最大值    
  11. int visited[maxNum][maxNum];//用来表示边visited[i][j]是否被访问过,初始化都是0  
  12. int set[maxNum];  
  13. //顶点信息    
  14. typedef struct    
  15. {    
  16.     int id;    
  17.     int dist;    
  18. }node;    
  19. //图的邻接矩阵表示结构        
  20. typedef struct        
  21. {        
  22.     //char v[maxNum];//图的顶点信息     
  23.     node v[maxNum];    
  24.     int e[maxNum][maxNum];//图的顶点信息        
  25.     int vNum;//顶点个数        
  26.     int eNum;//边的个数        
  27. }graph;    
  28. //函数声明      
  29. void createGraph(graph *g);//创建图g   
  30. void kruskal(graph *g);  
  31. void createGraph(graph *g)//创建图g        
  32. {        
  33.     cout<<"正在创建无向图..."<<endl;        
  34.     cout<<"请输入顶点个数vNum:";        
  35.     cin>>g->vNum;    
  36.     //cout<<"请输入边的个数eNum:";      
  37.  //   cin>>g->eNum;   
  38.     int i,j;      
  39.     //构造邻接矩阵,顶点到自身的距离是无穷大的。      
  40.     cout<<"输入邻接矩阵权值:"<<endl;     
  41.     for(i=1;i<=g->vNum;i++)    
  42.         for(j=1;j<=g->vNum;j++)    
  43.         {    
  44.             cin>>g->e[i][j];    
  45.             if(g->e[i][j]==0)    
  46.             {  
  47.                 g->e[i][j]=maxWeight;    
  48.             }  
  49.         }    
  50. }    
  51. void kruskal(graph *g)  
  52. {  
  53.     cout<<"最小生成树是:"<<endl;  
  54.     int k=1;  
  55.     int i,j;  
  56.     int a=1,b=1;  
  57.     int min=g->e[a][b];  
  58.     //初始化visited[][]  
  59.     for(i=1;i<=g->vNum;i++)  
  60.         for(j=1;j<=g->vNum;j++)  
  61.         {  
  62.             visited[i][j]=0;//表示边i-j没有被访问过  
  63.         }  
  64.     //初始化set[]  
  65.     for(i=1;i<=g->vNum;i++)  
  66.     {  
  67.         set[i]=i;  
  68.     }  
  69.     while(k<=g->vNum-1)//V-1次合并连通部件操作:union。v-1=e,就是查找出所有满足最小生成树的边  
  70.     {  
  71.         //找出最小边i->j  
  72.         for(i=1;i<=g->vNum;i++)  
  73.             for(j=1;j<=g->vNum;j++)  
  74.             {  
  75.                 if(g->e[i][j]<min&&visited[i][j]==0)  
  76.                 {  
  77.                     min=g->e[i][j];  
  78.                     a=i;  
  79.                     b=j;  
  80.                 }  
  81.             }  
  82.         visited[a][b]=1;  
  83.         visited[b][a]=1;  
  84.         min=maxWeight;  
  85.         if(set[a]!=set[b])//a b不在一个连通分量中,则合并  
  86.         {  
  87.             k++;//表中找到了一条合适的边  
  88.             cout<<a<<"->"<<b<<endl;  
  89.             //合并集合。将连同部件b合并到连同部件a中去。  
  90.             int temp_set=set[b];  
  91.             for(i=1;i<=g->vNum;i++)  
  92.             {  
  93.                 if(set[i]==temp_set)  
  94.                     set[i]=set[a];//将b合并到a中去。  
  95.                 cout<<set[i]<<" ";  
  96.             }  
  97.             cout<<endl;  
  98.         }  
  99.     }  
  100. }  
  101.         
  102. int main()        
  103. {        
  104.     graph *g;        
  105.     g=(graph*)malloc(sizeof(graph));        
  106.     createGraph(g);    
  107.     kruskal(g);  
  108.     int i;  
  109.     for(i=1;i<=g->vNum;i++)  
  110.         cout<<set[i]<<" ";  
  111.     cout<<endl;  
  112.     system("pause");      
  113.     return 0;        
  114. }        
  115. /*  
  116. 正在创建无向图... 
  117. 请输入顶点个数vNum: 
  118. 6 
  119. 输入邻接矩阵权值: 
  120. 0 5 6 4 0 0 
  121. 5 0 1 2 0 0 
  122. 6 1 0 2 5 3 
  123. 4 2 2 0 0 4 
  124. 0 0 5 0 0 4 
  125. 0 0 3 4 4 0 
  126. 最小生成树是: 
  127. 2->3 
  128. 1 2 2 4 5 6 
  129. 2->4 
  130. 1 2 2 2 5 6 
  131. 3->6 
  132. 1 2 2 2 5 2 
  133. 1->4 
  134. 1 1 1 1 5 1 
  135. 5->6 
  136. 5 5 5 5 5 5 
  137. 5 5 5 5 5 5 
  138. 请按任意键继续. . . 
  139. */   

3.单独提取合并集合的方法

为了是程序更加清晰,将合并集合的方法单独提取出来。代码实例如下:

  1. void union_set(graph *g,int a,int b)  
  2. {  
  3.     int i;  
  4.     //合并集合。将连同部件b合并到连同部件a中去。  
  5.     int temp_set=set[b];  
  6.     for(i=1;i<=g->vNum;i++)  
  7.     {  
  8.         if(set[i]==temp_set)  
  9.             set[i]=set[a];//将b合并到a中去。  
  10.         cout<<set[i]<<" ";  
  11.     }  
  12.     cout<<endl;  
  13. }  

修改以后原来的程序只稍作修改即可,在void kruskal(graph *g)中作如下修改:

  1. if(set[a]!=set[b])//a b不在一个连通分量中,则合并  
  2. {  
  3.     k++;//表中找到了一条合适的边  
  4.     cout<<a<<"->"<<b<<endl;  
  5.     union_set(g,a,b);//合并集合。  
  6. }  

 

 




本文转自xwdreamer博客园博客,原文链接:http://www.cnblogs.com/xwdreamer/archive/2011/06/15/2297001.html,如需转载请自行联系原作者

网友评论

登录后评论
0/500
评论
嗯哼9925
+ 关注