最小生成树之Kruskal法

在图论中，树是指无回路存在的连通图。一个连通图的生成树是指包含了所有顶点的树。如果把生成树的边的权值总和作为生成树的权，那么权值最小的生成树就称为最小生成树。因为最小生成树在实际中有很多应用，所以我们有必要了解怎样生成最小生成树。构造最小生成树的两种常用方法：Kruskal算法、Prim算法。本文介绍Kruskal算法，Prim算法在下篇文章中介绍。

Kruskal算法是从另一条途径来求网络的的最小生成树。设G=(V, E)是一个有n个顶点的连通图，则令最小生成树的初值状态为只有n个顶点而无任何边的非连通图T=(V, {空集})，此时图中每个顶点自成一个连通分量。按照权值递增的顺序依次选择E中的边，若该边依附于T中两个不同的连通分量，则将此边加入TE中，否则舍去此边而选择下一条代价最小的边，直到T中所有顶点都在同一连通分量上为止。这时的T，便是G的一棵最小生成树。

物理老师曾说过，图像比文字的信息量大得多，这可以从一幅图像和一篇文章所占电脑的存储空间大小明显得出。因此我们可以同下面的图解过程了解Kruskal算法的思想：

在该算法中，每次都要寻找最短边，如果用邻接矩阵实现的话，则需要对整个矩阵扫描一遍，时间复杂度较高，如果采用邻接表的话，由于每条边都被连接两次，使得寻找时间加倍。所以采用如下结构体：

//图的存储结构体
typedef struct
{
	int startvex,endvex;//边的两个顶点
	int length;//边长
	int sign;//是否被选择,1表示被选择，0表示未被选择，2表示选择后形成环，被抛弃
}edge;

具体的程序实现如下：

#include
  
   
#define M 10 //边数
#define N 6  //顶点数 

//图的存储结构体
typedef struct
{
	int startvex,endvex;//边的两个顶点
	int length;//边长
	int sign;//是否被选择,1表示被选择，0表示未被选择，2表示选择后形成环，被抛弃
}edge;
	edge T[M];
	int flag1[N];//标记顶点是否已被选中
void Kruskal(edge T[M],int *flag1)
{
	int i,j,k,l,min;
	int a[M]={0,0,0,1,1,1,2,3,3,4};//边的两个顶点及边的长度
	int b[M]={1,4,5,2,3,5,3,4,5,5};
	int c[M]={10,19,21,5,6,11,6,18,14,33};

	for(i=0;i
   
    
 
    
程序的结果与上面的图解的结果稍有不同，但是正确的，因为最小生成树有时候是不唯一的。
 
    

 
 
    
注：如果程序出错，可能是使用的开发平台版本不同，请点击如下链接： 解释说明