/**********************************************************************\
 功    能：  利用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;
}

评论