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