/**********************************************************************\ 功 能： 利用Kruscal算法求 " 无向图 " 的最小生成树 输入说明： 首先输入图的顶点数 n 边数 m 接着下一行每行输入每一条边 包括起点，终点，权值 (顶点从 1 开始编号) 输出说明： 输出最小生成树的各边，包括起点，终点，权值，最后输出总 的权值。 调试实例： 输入文件：( 用管道调试 ) 6 10 1 2 4 1 3 8 1 4 5 1 6 7 4 3 2 4 5 11 4 6 3 6 5 2 3 5 9 2 3 6 输出结果： The Graphy's smallest tree's sides as follow: start end 1 2 4 1 4 5 4 3 2 4 6 3 6 5 2 Total is :16 语 言： 非标准 C 编译环境：VC ++ 6.0 Author ： 江南孤峰 Time ：2006--11--1 \**********************************************************************/ #include <stdio.h>#include <process.h>#include <stdlib.h>#include <limits.h>#include <malloc.h>#include <string.h> typedef struct Side{ //边集包括 起点，终点，权值 int StartPoint; int EndPoint; int Value; struct Side *next;}DefSide; int main(){ int n,m,s,e,v,np,i,j; int *presult; //结果中用于存储节点编号的数组 int *meter;//邻接矩阵 DefSide *temp,*sides; //用于存最小生成树的边信息 scanf("%d%d",&n,&m); presult = (int *)malloc(sizeof(int) * n + 2); meter = (int *)malloc(sizeof(int) * n * n + 2); memset(meter,0,n * n * sizeof(int) + 2); for(j = i = 0; i < m; j = 0,i ++){ scanf("%d %d %d",&s,&e,&v); *(meter + (s-1)*n + e-1) = v; *(meter + (e-1)*n + s-1) = v; /* 注意如果是求有向图的最小生成树，只需将该付值语句注释掉 */ } temp=sides=(DefSide *)malloc(sizeof(DefSide)); for(np = presult[0] = 0; np < n; np ++){ //检查结果节点集是否已满 temp -> Value = INT_MAX; //初始化边链表节点的值 for(i = 0; i <= np; i ++){ //结果节点集里的节点做为起点 for(j = 0; j < n; j ++){ //寻找终点 for(s = 0; s <= np; s ++){ //如果该终点已在结果节点集中存在则放弃该终点 if(j == presult[s]){ s = -1; break; } } if(s == -1) //该终点不符合要求，选择下一个点 continue; //选择一条最短的边，存入结果的边链表中 if( *(meter + presult[i]*n + j) && *(meter + presult[i]*n + j) < temp->Value ){ temp->Value = *(meter + presult[i]*n + j); temp->StartPoint = presult[i]; temp->EndPoint = j; } } } presult[np+1] = temp->EndPoint; //更新结果节点集 temp -> next = (DefSide *)malloc(sizeof(DefSide)); //分配新的边链表节点 temp = temp -> next; } temp -> next = NULL; printf("The Graphy\'s smallest tree\'s sides as follow:\n"); printf("%-8s%-8s%-8s\n","start","end","Value"); for(v = i = 0,temp = sides,n --; i < n; i ++){//输出组成该图最小生成树的边，包括边的起点 ，终点，值 printf("%-8d%-8d%-8d\n",temp->StartPoint+1,temp->EndPoint+1,temp->Value); v += temp -> Value; sides = temp; temp = temp -> next; free(sides); } printf("Total value is :%d\n",v); free(temp); return EXIT_SUCCESS;}
评论