prim算法最小生成树.doc

#includemalloc.h #includestdlib.h #includestdio.h #include io.h #include windows.h #include limits.h #define MAX_VERTEX_NUM 20 // 最大顶点个数 #define MAX_NAME 3 // 顶点字符串的最大长度+1 #define MAX_INFO 20 // 相关信息字符串的最大长度+1 #define INFINITY INT_MAX // 用整型最大值代替∞ typedef int VRType; typedef char InfoType; typedef char VertexType[MAX_NAME]; // 邻接矩阵的数据结构 typedef struct { VRType adj; // 顶点关系类型。对无权图，用1(是)或0(否)表示相邻否； // 对带权图，则为权值类型 InfoType *info; // 该弧相关信息的指针(可无) }ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 图的数据结构 typedef struct { VertexType vexs[MAX_VERTEX_NUM]; // 顶点向量 AdjMatrix arcs; // 邻接矩阵 int vexnum, // 图的当前顶点数 arcnum; // 图的当前弧数 } MGraph; // 记录从顶点集U到V-U的代价最小的边的辅助数组定义 typedef struct { VertexType adjvex; VRType lowcost; }minside[MAX_VERTEX_NUM]; // 若G中存在顶点u,则返回该顶点在图中位置;否则返回-1。 int LocateVex(MGraph G,VertexType u) { int i; for(i = 0; i G.vexnum; ++i) if( strcmp(u, G.vexs[i]) == 0) return i; return -1; } // 算法7.2 P162 // 采用数组(邻接矩阵)表示法,构造无向网G。 int CreateAN(MGraph *G) { int i,j,k,w,IncInfo; char s[MAX_INFO],*info; VertexType va,vb; printf(请输入无向网G的顶点数,边数,边是否含其它信息(是:1,否:0):(空格区分) ); scanf(%d%d%d%*c,(*G).vexnum,(*G).arcnum,IncInfo); printf(请输入%d个顶点的值(%d个字符):\n,(*G).vexnum,MAX_NAME); for(i=0;i(*G).vexnum;++i) // 构造顶点向量 scanf(%s,(*G).vexs[i]); for(i=0;i(*G).vexnum;++i) // 初始化邻接矩阵 for(j=0;j(*G).vexnum;++j) { (*G).arcs[i][j].adj=INFINITY; // 网初始化为无穷大 (*G).arcs[i][j].info=NULL; } printf(请输入%d条边的顶点1 顶点2 权值(以空格作为间隔): \n,(*G).arcnum); for(k=0;k(*G).arcnum;++k) { scanf(%s%s%d%*c,va,vb,w); // %*c吃掉回车符 i=LocateVex(*G,va); j=LocateVex(*G,vb); (*G).arcs[i][j].adj=(*G).arcs[j][i].adj=w; // 无向 if(IncInfo) { printf(请输入该边的相关信息(%d个字符): ,MAX_INFO); gets(s); w=strlen(s); if(w) { info=(char*)malloc((w+1)*sizeof(char)); strcpy(info,s); (*G).arcs[i][j].info=(*G).arcs[j][i].info=info; // 无向 } } } return 1; } // 求closedge.lowcost的最小正值 int minimum(minside SZ,MGraph G) { i