c代码普利姆.doc

普里姆算法实现数据结构 2009-10-29 17:04:24 阅读 362 评论 0字号: 大中小#include <> #include <> #include <> #define INFINITY INT_MAX //INT_MAX 表示最大整数,请参阅 C的 文件#define n 10 //图的顶点数,应由用户定义 typedef int AdjMatrix[n][n]; //用二维数组作为邻接矩阵表示//树边结点 typedef struct{ int fromvex,tovex; //边的起点和终点 int length; //边上的权}TreeEdgeNode; typedef TreeEdgeNode MST[n-1]; //最小生成树类型 AdjMatrix G; //连通网的带权邻接矩阵,作为 Prim 算法的输入 MST T; //存放 G的最小生成树,作为 Prim 算法的输出//打印错误信息 void Error(char *msg) { printf("%c\n",msg); } // void CreateGraph(AdjMatrix G) { int i,j; int start,end,weight; for(i=0;i<n;i++) //n 为图的顶点数 for(j=0;j<n;j++) G[i][j] = INFINITY; //INFINITY 代表无穷大 printf(" 输入弧和其权值,格式:弧尾,弧头,权值\n"); for(i=0;i<n-1;i++){ scanf("%d %d %d",&start,&end,&weight); getchar(); G[start][end]=weight; G[end][start]=weight; }} void DefaultCreateGraph(AdjMatrix G){ int i,j; for(i=0;i<n;i++) //n 为图的顶点数 for(j=0;j<n;j++) G[i][j] = INFINITY; //0-9 G[0][1]=4; G[1][0]=4; G[1][2]=2; G[2][1]=2; G[0][3]=3; G[3][0]=3; G[1][5]=1; G[5][1]=1; G[3][6]=10; G[6][3]=10; G[6][9]=5; G[9][6]=5; G[9][7]=2; G[7][9]=2; G[7][8]=6; G[8][7]=6; G[3][4]=8; G[4][3]=8; G[4][5]=1; G[5][4]=1; G[2][5]=2; G[5][2]=2; G[4][7]=4; G[7][4]=4; G[5][8]=4; G[8][5]=4; } //构造初始的时候选轻边集 T[0...n-2] ,树边集 TE!=Null, 红点集 U={r} void InitCandidateSet(AdjMatrix G,MST T,int r){ int i,k=0; for(i=0;i<n;i++) //依次行成每个蓝点 i初始的最短紫边存放在 T[k] 中 if(i!=r){ //i是蓝点(r,i) 是紫边 T[k].fromvex = r