c/c++语言开发共享数据结构（C实现）——- 最小生成树之Kruskal算法

算法描述：

kruskal算法是按权值递增的次序来构造最小生成树的方法。

　　　假设g(v,e)最一个具有n个顶点的连通网，顶点集v={v1,v2,….,vn}。设所求的最小生成树为t={u,te},其中u是t的顶点集，te是ｔ的边集，u和te的初始值为空集。kruskal算法的基本思想如下：将最小生成树初始化为t=(v,te),仅包含 g的全部顶点，不包含g的任一条边，此时，t由n 个连通分量组成，每个分量只有一个顶点；将图中g中的边按权值从小到大排序，选择代价最小了一条边，若该边所依附的顶点分属于t中的不同的连通分量，则将此边加入到te中，否则，舍弃此边而选择下一条代价最小的边。依次类推，直至te中包含n-1条边（即t中所有的顶点都在同一连通分量上）为止。

算法实现：

　　　设置一个edge数组存储连通网中所有的边，为了便于选择当前权值最小的边，需要将edge中的边按权值从小到大进行排列。

　　　而在连通分量的合并上，可以采用集合的合并方法，对于有n个顶点的连通网，设置一个数组father[0…n-1]，其初始值为-1,表示n个顶点在不同的连通分量上。然后，依次扫描edge数组中的每一条边，并查找相关联的两个顶点所属的连通分量，假设vf1和vf2为两个顶点的所在树的根节点的序号，若vf1不等于vf2，则表明这条边的两个顶点不属于同一个连通分量，则将这条边作为最小生成树的边并输出，然后合并它们所属的两个连通分量。

算法代码：

 int findfather(int father[],int v){ 	int t = v; 	while(father[t] != -1) 		t = father[t]; 	return t; }    /* *  *kruskal算法求最小生成树  * */  void kruskal_mg(mgraph mg,edge edge[]){ 	int father[max_vex_num]; 	int i,count,vf1,vf2; 	// 初始化father数组 	for(i = 0;i < max_vex_num;i++){ 		father[i] = -1; 	} 	i = 0; 	count = 0; // 统计加入最小生树中的边数 	// 遍历任意两个结点之间的边 	while(i < mg.arcnum && count < mg.arcnum){ 		vf1 = findfather(father,edge[i].start); 		vf2 = findfather(father,edge[i].end); 		// 如果这两个节点不属于同一个连通分量，则加入同一个连通分量 		if (vf1 != vf2){ 			father[vf2] = vf1; 			count++; 			printf(%c,%c,%d ,mg.vexs[edge[i].start],mg.vexs[edge[i].end],edge[i].cost); 		} 		i++; 	} }

　　　其中，函数findfather的作用就是找指定节点所属的连通分量，在这里也就是找其所在树的根节点在数组中的序号。

算法说明：

　　　对于带权图g中e条边的权值的排序方法可以有多种，这里采用的是最简单的冒泡排序法，时间复杂度为o(n^2)。而判断新选择的边的两个顶点是否在同一个连通分量中，这个问题等价于一个在最多有n 个顶点的生成树中遍历寻找新选择的边的两个节点是否存在的问题，所以此算法的复杂度最坏情况下是o(n^2)。

　　　注意：一般来讲，prim算法的时间复杂度为o(n^2),因此适合于稠密图，而kruskal算法需要对e条边进行排序，最快的情况下复杂度为o(elog2e)，因此对于稀疏图，采用kruskal算法比较合适。

完整代码：

 /*  * =====================================================================================  *  *       filename:  kruskal.c  *  *    description:  最小生成树之kruskal算法  *  *        version:  1.0  *        created:  2015年05月06日 21时25分12秒  *       revision:  none  *       compiler:  gcc  *  *         author:  jesson20121020 (), 997287955@qq.com  *   organization:    *  * =====================================================================================  */   #include  #include  #define max_vex_num 50 #define max_arc_num 100 #define un_reach 1000     typedef char vertextype; typedef enum { 	dg, udg } graphtype; typedef struct { 	vertextype vexs[max_vex_num]; 	int arcs[max_vex_num][max_vex_num]; 	int vexnum, arcnum; 	graphtype type; } mgraph;    /**  * 根据名称得到指定顶点在顶点集合中的下标  * vex  顶点  * return 如果找到，则返回下标，否则，返回０  */ int getindexofvexs(char vex, mgraph *mg) { 	int i; 	for (i = 1; i <= mg->vexnum; i++) { 		if (mg->vexs[i] == vex) { 			return i; 		} 	} 	return 0; }  /**  * 创建邻接矩阵  */ void create_mg(mgraph *mg) { 	int i, j, k,weight; 	int v1, v2, type; 	char c1, c2; 	printf(please input graph type dg(0) or udg(1) :); 	scanf(%d, &type); 	if (type == 0) 		mg->type = dg; 	else if (type == 1) 		mg->type = udg; 	else { 		printf(please input correct graph type dg(0) or udg(1)!); 		return; 	}  	printf(please input vexmun : ); 	scanf(%d, &mg->vexnum); 	printf(please input arcnum : ); 	scanf(%d, &mg->arcnum); 	getchar(); 	for (i = 1; i <= mg->vexnum; i++) { 		printf(please input %dth vex(char):, i); 		scanf(%c, &mg->vexs[i]); 		getchar(); 	}  	//初始化邻接矩阵 	for (i = 1; i <= mg->vexnum; i++) { 		for (j = 1; j <= mg->vexnum; j++) { 			if(i == j) 				mg->arcs[i][j] = 0; 			else 				mg->arcs[i][j] = un_reach; 		} 	}  	//输入边的信息，建立邻接矩阵 	for (k = 1; k <= mg->arcnum; k++) { 		printf(please input %dth arc v1(char) v2(char) weight(int): , k);  		scanf(%c %c %d, &c1, &c2,&weight); 		v1 = getindexofvexs(c1, mg); 		v2 = getindexofvexs(c2, mg); 		if (mg->type == 1) 			mg->arcs[v1][v2] = mg->arcs[v2][v1] = weight; 		else 			mg->arcs[v1][v2] = weight; 		getchar(); 	}     } /**  * 打印邻接矩阵和顶点信息  */ void print_mg(mgraph mg) { 	int i, j; 	if(mg.type == dg){ 		printf(graph type: direct graph ); 	} 	else{ 		printf(graph type: undirect graph ); 	}  	printf(graph vertex number: %d ,mg.vexnum); 	printf(graph arc number: %d ,mg.arcnum);  	printf(vertex set:  ); 	for (i = 1; i <= mg.vexnum; i++) 		printf(%c	, mg.vexs[i]); 	printf( adjacency matrix: );  	for (i = 1; i <= mg.vexnum; i++) { 		j = 1; 		for (; j < mg.vexnum; j++) { 			printf(%d	, mg.arcs[i][j]); 		} 		printf(%d , mg.arcs[i][j]); 	} }   // 定义边结构体 typedef struct{ 	int start; 	int end; 	int cost; }edge;   /* *  * 由邻接矩阵得到边的信息  *  * */ void init_edge(mgraph mg,edge edge[]){ 	int i,j; 	int count = 0; 	if(mg.type == 0){ 		for(i = 1; i <= mg.vexnum;i++){ 			for (j = 1;j <= mg.vexnum;j++){ 				if(mg.arcs[i][j] != 0 && mg.arcs[i][j] != un_reach){ 					edge[count].start = i; 					edge[count].end = j; 					edge[count].cost = mg.arcs[i][j]; 					count++; 				} 			} 		} 	} 	else{ 		for(i = 1; i <= mg.vexnum;i++){ 			for (j = i;j <= mg.vexnum;j++){ 				if(mg.arcs[i][j] != 0 && mg.arcs[i][j] != un_reach){ 					edge[count].start = i; 					edge[count].end = j; 					edge[count].cost = mg.arcs[i][j]; 					count++; 				} 			} 		} 	} 	 }     /* *  *　将边按权值从大到小排序  * */ void sort_edge(edge edge[],int arcnum){ 	int i,j; 	edge temp; 	for(i = 0; i < arcnum - 1;i++){ 		for (j = i+1;j < arcnum;j++){ 			if(edge[i].cost > edge[j].cost){ 				temp = edge[i]; 				edge[i] = edge[j]; 				edge[j] = temp; 			} 		} 	} }  /* *  * 输出边的信息  * */ void print_edge(edge edge[],int arcnum){ 	int i = 0; 	while(i < arcnum){ 		printf(%d,%d,%d ,edge[i].start,edge[i].end,edge[i].cost); 		i++; 	} } /** *    找出指定节点的所属的连通分量，这里是找出其根节点在father数组中下标。 **/ int findfather(int father[],int v){ 	int t = v; 	while(father[t] != -1) 		t = father[t]; 	return t; }  /* *  *kruskal算法求最小生成树  * */  void kruskal_mg(mgraph mg,edge edge[]){ 	int father[max_vex_num]; 	int i,count,vf1,vf2; 	// 初始化father数组 	for(i = 0;i < max_vex_num;i++){ 		father[i] = -1; 	} 	i = 0; 	count = 0; // 统计加入最小生树中的边数 	// 遍历任意两个结点之间的边 	while(i < mg.arcnum && count < mg.arcnum){ 		vf1 = findfather(father,edge[i].start); 		vf2 = findfather(father,edge[i].end); 		// 如果这两个节点不属于同一个连通分量，则加入同一个连通分量 		if (vf1 != vf2){ 			father[vf2] = vf1; 			count++; 			printf(%c,%c,%d ,mg.vexs[edge[i].start],mg.vexs[edge[i].end],edge[i].cost); 		} 		i++; 	} } /**  * 主函数  */ int main(void) { 	mgraph mg; 	edge edge[max_arc_num]; 	create_mg(&mg); 	print_mg(mg); 	init_edge(mg,edge); 	sort_edge(edge,mg.arcnum); 	printf(the result of kruskal: ); 	kruskal_mg(mg,edge);  		 	 	return exit_success; }  

运行演示：

 jesson@jesson-k43sv:~/develop/worksapce/c_learning/最小生成树$ gcc -o kruskal kruskal.c jesson@jesson-k43sv:~/develop/worksapce/c_learning/最小生成树$ ./kruskal  please input graph type dg(0) or udg(1) :0 please input vexmun : 4 please input arcnum : 5 please input 1th vex(char):a   please input 2th vex(char):b please input 3th vex(char):c please input 4th vex(char):d please input 1th arc v1(char) v2(char) weight(int): a b 1 please input 2th arc v1(char) v2(char) weight(int): a c 3 please input 3th arc v1(char) v2(char) weight(int): a d 4 please input 4th arc v1(char) v2(char) weight(int): b c 2  please input 5th arc v1(char) v2(char) weight(int): c d 3 graph type: direct graph graph vertex number: 4 graph arc number: 5 vertex set:  a	b	c	d	 adjacency matrix: 0	1	3	4 1000	0	2	1000 1000	1000	0	3 1000	1000	1000	0 the result of kruskal: a,b,1 b,c,2 c,d,3