算法基本思想

       求加权连通图的最小生成树的算法。kruskal算法总共选择n- 1条边，所使用的贪婪准则是：从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合中。注意到所选取的边若产生环路则不可能形成一棵生成树。kruskal算法分e 步，其中e 是网络中边的数目。按耗费递增的顺序来考虑这e 条边，每次考虑一条边。当考虑某条边时，若将其加入到已选边的集合中会出现环路，则将其抛弃，否则，将它选入。

代码采用邻接矩阵表示图，采用边集表示法，代码将大大简化。代码中很多地方可以优化，因为只是用来学习算法，没有去优化。

完整C代码

/* 最小生成树的Kruskal算法 */

#include 
#include 
#include 

#define MaxSize 20

typedef char VertexType;

typedef struct Graph {		//定义图的邻接矩阵表示法结构
	VertexType ver[MaxSize+1];
	int edg[MaxSize][MaxSize];
}Graph;

typedef struct gEdge {		//定义一个边集结构，用来存储图的所有边信息
	int begin;
	int end;
	int weight;
}gEdge;

void CreateGraph( Graph *g )		//邻接矩阵法图的生成函数
{
	int i = 0;
	int j = 0;
	int VertexNum;
	VertexType Ver;

	printf("请输入图的顶点:\n");
	while( '\n' != (Ver=getchar()) ) {
		g->ver[i++] = Ver;
	}
	g->ver[i] = '\0';

	VertexNum = strlen(g->ver);
	printf("请输入相应的的邻接矩阵:\n");
	for( i=0; iedg[i][j]);
}

void PrintGraph( Graph g )		//打印图的结点标识符和邻接矩阵
{
	int i, j;
	int VertexNum = strlen(g.ver);
	printf("图的顶点为:\n");
	for( i=0; i p[j].weight ) {
				temp = p[i];
				p[i] = p[j];
				p[j] = temp;
			}

	return p;
}

//Kruskal算法生成MST
void Kruskal( Graph g )
{
	int VertexNum = CalVerNum( g );
	int EdgNum = CalEdgNum( g );
	gEdge *p = CreateEdges( g );
	int *index = (int *)malloc(sizeof(int)*VertexNum);		    //index数组，其元素为连通分量的编号，index[i] = index[j] 表示编号为i 和 j的顶点在同一个连通分量中，反之则不在同一个连通分量
	int *MSTEdge = (int *)malloc(sizeof(int)*VertexNum-1);		//MSTEdge数组，用来存储已确定的MST的边的编号，共VertexNum-1条边
	int k= 0;
	int WeightSum = 0;
	int IndexBegin, IndexEnd;

	for(int i=0; i=0 && index[p[j].end]>=0 && index[p[j].begin]==index[p[j].end]) ) {  //找到当前还没加入到同一个连通分量且权值最下的边
				MSTEdge[i] = j;		//将其加入到MST中去

				if( (-1 == index[p[j].begin]) && (-1 == index[p[j].end]) )			//该边的两个顶点都没加入过任何一个连通分量
					index[p[j].begin] = index[p[j].end] = i;	

				else if( (-1 == index[p[j].begin]) && (index[p[j].end] >= 0) ) {	//该边的尾end已在一个连通分量，头begin未加入过任何连通分量
					index[p[j].begin] = i;
					IndexEnd = index[p[j].end];
					for(int n=0; n= 0) ) {	//该边的头begin已在一个连通分量，尾end未加入过任何连通分量
					index[p[j].end] = i;
					IndexBegin = index[p[j].begin];
					for(int n=0; n
测试数据和结果
测试的图为：

测试通过