Kurskal算法生成最小生成树MST-白红宇

1.解析

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

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

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

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

2.算法实例

[c-sharp]
#include<iostream>        
#include<malloc.h>        
#include<queue>      
#include <algorithm>       
#include<stdlib.h>      
#include<functional>    
using namespace std;        
    
#define maxNum 100 //定义邻接举证的最大定点数      
#define maxWeight 1000000 //边权最大值    
int visited[maxNum][maxNum];//用来表示边visited[i][j]是否被访问过，初始化都是0  
int set[maxNum];  
//顶点信息    
typedef struct    
{    
    int id;    
    int dist;    
}node;    
//图的邻接矩阵表示结构        
typedef struct        
{        
    //char v[maxNum];//图的顶点信息     
    node v[maxNum];    
    int e[maxNum][maxNum];//图的顶点信息        
    int vNum;//顶点个数        
    int eNum;//边的个数        
}graph;    
//函数声明      
void createGraph(graph *g);//创建图g   
void kruskal(graph *g);  
void createGraph(graph *g)//创建图g        
{        
    cout<<"正在创建无向图..."<<endl;        
    cout<<"请输入顶点个数vNum:";        
    cin>>g->vNum;    
    //cout<<"请输入边的个数eNum:";      
 //   cin>>g->eNum;   
    int i,j;      
    //构造邻接矩阵，顶点到自身的距离是无穷大的。      
    cout<<"输入邻接矩阵权值："<<endl;     
    for(i=1;i<=g->vNum;i++)    
        for(j=1;j<=g->vNum;j++)    
        {    
            cin>>g->e[i][j];    
            if(g->e[i][j]==0)    
            {  
                g->e[i][j]=maxWeight;    
            }  
        }    
}    
void kruskal(graph *g)  
{  
    cout<<"最小生成树是："<<endl;  
    int k=1;  
    int i,j;  
    int a=1,b=1;  
    int min=g->e[a][b];  
    //初始化visited[][]  
    for(i=1;i<=g->vNum;i++)  
        for(j=1;j<=g->vNum;j++)  
        {  
            visited[i][j]=0;//表示边i-j没有被访问过  
        }  
    //初始化set[]  
    for(i=1;i<=g->vNum;i++)  
    {  
        set[i]=i;  
    }  
    while(k<=g->vNum-1)//V-1次合并连通部件操作：union。v-1=e，就是查找出所有满足最小生成树的边  
    {  
        //找出最小边i->j  
        for(i=1;i<=g->vNum;i++)  
            for(j=1;j<=g->vNum;j++)  
            {  
                if(g->e[i][j]<min&&visited[i][j]==0)  
                {  
                    min=g->e[i][j];  
                    a=i;  
                    b=j;  
                }  
            }  
        visited[a][b]=1;  
        visited[b][a]=1;  
        min=maxWeight;  
        if(set[a]!=set[b])//a b不在一个连通分量中，则合并  
        {  
            k++;//表中找到了一条合适的边  
            cout<<a<<"->"<<b<<endl;  
            //合并集合。将连同部件b合并到连同部件a中去。  
            int temp_set=set[b];  
            for(i=1;i<=g->vNum;i++)  
            {  
                if(set[i]==temp_set)  
                    set[i]=set[a];//将b合并到a中去。  
                cout<<set[i]<<" ";  
            }  
            cout<<endl;  
        }  
    }  
}  
        
int main()        
{        
    graph *g;        
    g=(graph*)malloc(sizeof(graph));        
    createGraph(g);    
    kruskal(g);  
    int i;  
    for(i=1;i<=g->vNum;i++)  
        cout<<set[i]<<" ";  
    cout<<endl;  
    system("pause");      
    return 0;        
}        
/*  
正在创建无向图... 
请输入顶点个数vNum: 
6 
输入邻接矩阵权值： 
0 5 6 4 0 0 
5 0 1 2 0 0 
6 1 0 2 5 3 
4 2 2 0 0 4 
0 0 5 0 0 4 
0 0 3 4 4 0 
最小生成树是： 
2->3 
1 2 2 4 5 6 
2->4 
1 2 2 2 5 6 
3->6 
1 2 2 2 5 2 
1->4 
1 1 1 1 5 1 
5->6 
5 5 5 5 5 5 
5 5 5 5 5 5 
请按任意键继续. . . 
*/   

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

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

[c-sharp]
void union_set(graph *g,int a,int b)  
{  
    int i;  
    //合并集合。将连同部件b合并到连同部件a中去。  
    int temp_set=set[b];  
    for(i=1;i<=g->vNum;i++)  
    {  
        if(set[i]==temp_set)  
            set[i]=set[a];//将b合并到a中去。  
        cout<<set[i]<<" ";  
    }  
    cout<<endl;  
}  

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

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

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