（写于December 13th, 2012）
Kruskal算法的基本思想：
设有一个有n个顶点的连通网N={V,E},将N中的边按照权值从小到大的顺序排列。
①将n个顶点看成n个集合；
②按权值由小到大的顺序选择边，所选边应满足两个顶点不在同一个顶点集合内，将该边放到生成树边的集合中，同时将该边的两个顶点所在的顶点集合合并。
③重复②直到所有的顶点都在同一个顶点集合内。
其实这个算法理解起来挺容易的，但是我在实现的过程中遇到最大的困难就是对于点集的划分和查找，最后就想到了要用到并查集，也就是说可以先把每个顶点都看成一个点集，然后每次添加边可以把边看做是等价关系中的一对序偶关系，这样,每次添加边的过程相当于对一个集合进行等价类的划分。
这是我用c实现的代码：
主函数:
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include <limits.h>
#include"adjmatrix.h"
#include"vexnum.h"
int main()
{
AdjMatrix G;
vex ver[MAX_VERTEX_NUM];
ParentTree min;
int i;
CreateDN(&G);//创建网
printf("邻接矩阵:\n");
printadj(G);//打印矩阵
order(&G,ver);//根据权值大小排序
printf("网中所有边的按照权值大小排序:\n");
for(i=0;i<G.arcnum;i++)
{
printf("(%c,%c):%d\n",ver[i].start,ver[i].end,ver[i].weight);
}
select(ver,&min,G);
return 0;
}
adjmatrix.h文件:
#define MAX_VERTEX_NUM 20
#define INFINITY INT_MAX
typedef struct ArcNode
{
int adj;
}ArcNode;
typedef struct
{
char vertex[MAX_VERTEX_NUM];
ArcNode arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
int vexnum,arcnum;//图的顶点数和弧数
}AdjMatrix;
int LocateVertex(AdjMatrix *G,char v)
{
int j=-1,k;
for(k=0;k<G->vexnum;k++)
if(G->vertex[k]==v)
{
j=k;
break;
}
return j;
}
int CreateDN(AdjMatrix *G)
{
int i,j,k,weight;
char v1,v2;
printf("请输入图的顶点数和弧数:\n");
scanf("%d,%d",&G->vexnum,&G->arcnum);
getchar();
for(i=0;i<G->vexnum;i++)
{
for(j=0;j<G->vexnum;j++)
{
G->arcs[i][j].adj=INFINITY;
}
}
printf("输入图的定点:\n");
for(i=0;i<G->vexnum;i++)
{
scanf("%c",&G->vertex[i]);
getchar();
}
printf("依次输入弧的两个顶点及权值:\n");
for(k=0;k<G->arcnum;k++)
{
scanf("%c,%c,%d",&v1,&v2,&weight);
getchar();
i=LocateVertex(G,v1);
j=LocateVertex(G,v2);
if(i!=-1&&j!=-1)
{
G->arcs[i][j].adj=weight;
G->arcs[j][i].adj=weight;
}
else
{
printf("顶点找不到!\n");
exit(1);
}
}
return 0;
}
int printadj(AdjMatrix G)//打印邻接矩阵
{
int i,j;
for(i=0;i<G.vexnum;i++)\
{
for(j=0;j<G.vexnum;j++)
{
if(G.arcs[i][j].adj==INFINITY)
printf("~ ");
else
printf("%d ",G.arcs[i][j].adj);
}
printf("\n");
}
return 0;
}vexnum.h文件:
typedef struct
{
char start;
char end;
int weight;//权值
}vex;//存放每条边的信息
typedef struct TNode
{
char data;
int parent;//标志每个结点是否属于同一个点集
}TNode;
typedef struct
{
TNode tree[MAX_VERTEX_NUM];
int nodenum;//结点数
}ParentTree;//点集(利用并查集)
//根据权值大小为边集排序
int order(AdjMatrix *G,vex ver[MAX_VERTEX_NUM])
{
int i,j,k=0,change=1,cost;
char v1,v2;
//初始化
for(i=0;i<G->vexnum;i++)
{
for(j=i;j<G->vexnum;j++)
{
if(G->arcs[i][j].adj!=INFINITY)
{
ver[k].start=G->vertex[i];
ver[k].end=G->vertex[j];
ver[k].weight=G->arcs[i][j].adj;
k++;
}
}
}
for(i=0;i<G->arcnum-1&&change==1;i++)
{
change=0;
for(j=0;j<G->arcnum-i-1;j++)
{
if(ver[j].weight>ver[j+1].weight)
{
v1=ver[j].start;
v2=ver[j].end;
cost=ver[j].weight;
ver[j].start=ver[j+1].start;
ver[j].end=ver[j+1].end;
ver[j].weight=ver[j+1].weight;
ver[j+1].start=v1;
ver[j+1].end=v2;
ver[j+1].weight=cost;
change=1;
}
}
}
return 0;
}
//查找元素的下标
int Locate(ParentTree min,char v)
{
int i;
for(i=0;i<min.nodenum;i++)
{
if(min.tree[i].data==v)
return i;
}
return -1;
}
//从新划分等价类(parent相等为一个等价类集合)
void change(ParentTree *min,int b,int a)
{
int i,n=min->tree[b].parent;
for(i=0;i<min->nodenum;i++)
{
if(min->tree[i].parent==n)
{
min->tree[i].parent=min->tree[a].parent;
}
}
}
//选择最小的权值并且顶点不在同一个集合内放入生成树边的集合中
int select(vex ver[MAX_VERTEX_NUM],ParentTree *min,AdjMatrix G)
{
int i,a,b;
min->nodenum=G.vexnum;
for(i=0;i<G.vexnum;i++)
{
min->tree[i].parent=i;//初始让每个结点都个子为一个集合
min->tree[i].data=G.vertex[i];
}//初始化并查集
printf("最小生成树:\n");
for(i=0;i<G.arcnum;i++)
{
a=Locate(*min,ver[i].start);
b=Locate(*min,ver[i].end);
if(min->tree[a].parent!=min->tree[b].parent)
{
printf("(%c,%c) ",ver[i].start,ver[i].end);//若不属于同一个点集则输出最小生成树
change(min,b,a);//将新入的边集划分到点集中
}
}
printf("\n");
return 0;
} 对于下图：（自己画的，比较简陋）
程序输入：
运行结果：
学弱花了不少时间终于将它实现好啦~最大的感受就是用离散数学中的知识虽然很快就可以理解的算法思想，但是实现起来还有一定的距离。