1.解析
while循环其实不是只循环V-1次，因为如果找出的边能够形成环的话，这条边并不是我们需要的边，所以本次循环无效。while循环中其实包含了找出最小的功能，这个其实可以通过单独的一个函数来实现。就是按边长度升序来排列。
kruskal算法其实是一个找边的算法，对于一V个顶点的图，必定由V-1条边构成一个最小生成树，那么按边的权值遍历图每一条边。判断如果添加这条选出的当前权最小的边，图中会不会生成一个环，如果生成环，则当前找到的这条边无效，继续找下一条权值最小边。
每找出一条边，相当于图中合并了两个连通部件（初始化是一个顶点算一个连通部件），因此找到V-1条边就相当于是将原来分离的V个连通部件合并成一个更大的连通部件。
在两个连通部件之间添加一条边，会组成一个更大的连通部件，并且不存在环。
2.算法实例
- #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.单独提取合并集合的方法
为了是程序更加清晰，将合并集合的方法单独提取出来。代码实例如下：
- 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)中作如下修改：
- 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，如需转载请自行联系原作者
