用计算机实现图论中的最短路径程序.zip_图论解决最短路径

/* bo7-1.c 图的数组(邻接矩阵)存储(存储结构由c7-1.h定义)的基本操作(20个) */ int LocateVex(MGraph G,VertexType u) { /* 初始条件:图G存在,u和G中顶点有相同特征 */ /* 操作结果:若G中存在顶点u,则返回该顶点在图中位置;否则返回-1 */ int i; for(i=0;i<G.vexnum;++i) if(strcmp(u,G.vexs[i])==0) return i; return -1; } Status CreateFAG(MGraph *G) { /* 采用数组(邻接矩阵)表示法,由文件构造没有相关信息的无向图G */ int i,j,k; char filename[13]; VertexType va,vb; FILE *graphlist; printf("请输入数据文件名(f7-1.dat)："); scanf("%s",filename); graphlist=fopen(filename,"r"); fscanf(graphlist,"%d",&(*G).vexnum); fscanf(graphlist,"%d",&(*G).arcnum); for(i=0;i<(*G).vexnum;++i) /* 构造顶点向量 */ fscanf(graphlist,"%s",(*G).vexs[i]); for(i=0;i<(*G).vexnum;++i) /* 初始化邻接矩阵 */ for(j=0;j<(*G).vexnum;++j) { (*G).arcs[i][j].adj=0; /* 图 */ (*G).arcs[i][j].info=NULL; /* 没有相关信息 */ } for(k=0;k<(*G).arcnum;++k) { fscanf(graphlist,"%s%s",va,vb); i=LocateVex(*G,va); j=LocateVex(*G,vb); (*G).arcs[i][j].adj=(*G).arcs[j][i].adj=1; /* 无向图 */ } fclose(graphlist); (*G).kind=AG; return OK; } Status CreateDG(MGraph *G) { /* 采用数组(邻接矩阵)表示法,构造有向图G */ int i,j,k,l,IncInfo; char s[MAX_INFO],*info; VertexType va,vb; printf("请输入有向图G的顶点数,弧数,弧是否含其它信息(是:1,否:0): "); scanf("%d,%d,%d",&(*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=0; /* 图 */ (*G).arcs[i][j].info=NULL; } printf("请输入%d条弧的弧尾 弧头(以空格作为间隔): \n",(*G).arcnum); for(k=0;k<(*G).arcnum;++k) { scanf("%s%s%*c",va,vb); /* %*c吃掉回车符 */ i=LocateVex(*G,va); j=LocateVex(*G,vb); (*G).arcs[i][j].adj=1; /* 有向图 */ if(IncInfo) { printf("请输入该弧的相关信息(<%d个字符): ",MAX_INFO); gets(s); l=strlen(s); if(l) { info=(char*)malloc((l+1)*sizeof(char)); strcpy(info,s); (*G).arcs[i][j].info=info; /* 有向 */ } } } (*G).kind=DG; return OK; } Status CreateDN(MGraph *G) { /* 采用数组(邻接矩阵)表示法,构造有向网G */ int i,j,k,w,IncInfo; char s[MAX_INFO],*info; VertexType va,vb; printf("请输入有向网G的顶点数,弧数,弧是否含其它信息(是:1,否:0): "); scanf("%d,%d,%d",&(*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条弧的弧尾 弧头 权值(以空格作为间隔): \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=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=info; /* 有向 */ } } } (*G).kind=DN; return OK; } Status CreateAG(MGraph *G) { /* 采用数组(邻接矩阵)表示法,构造无向图G */ int i,j,k,l,IncInfo; char s[MAX_INFO],*info; VertexType va,vb; printf("请输入无向图G的顶点数,边数,边是否含其它信息(是:1,否:0): "); scanf("%d,%d,%d",&(*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=0; /* 图 */ (*G).arcs[i][j].info=NULL; } printf("请输入%d条边的顶点1 顶点2(以空格作为间隔): \n",(*G).arcnum); for(k=0;k<(*G).arcnum;++k) { scanf("%s%s%*c",va,vb); /* %*c吃掉回车符 */ i=LocateVex(*G,va); j=LocateVex(*G,vb); (*G).arcs[i][j].adj=(*G).arcs[j][i].adj=1; /* 无向图 */ if(IncInfo) { printf("请输入该边的相关信息(<%d个字符): ",MAX_INFO); gets(s); l=strlen(s); if(l) { info=(char*)malloc((l+1)*sizeof(char)); strcpy(info,s); (*G).arcs[i][j].info=(*G).arcs[j][i].info=info; /* 无向 */ } } } (*G).kind=AG; return OK; } Status CreateAN(MGraph *G) { /* 采用数组(邻接矩阵)表示法,构造无向网G。算法7.2 */ int i,j,k,w,IncInfo; char s[MAX_INFO],*info; VertexType va,vb; printf("请输入无向网G的顶点数,边数,边是否含其它信息(是:1,否:0): "); scanf("%d,%d,%d",&(*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; /* 无向 */ } } } (*G).kind=AN; return OK; } Status CreateGraph(MGraph *G) { /* 采用数组(邻接矩阵)表示法,构造图G。算法7.1 */ printf("请输入图G的类型(有向图:0,有向网:1,无向图:2,无向网:3): "); scanf("%d",&(*G).kind); switch((*G).kind) { case DG: return CreateDG(G); /* 构造有向图 */ case DN: return CreateDN(G); /* 构造有向网 */ case AG: return CreateAG(G); /* 构造无向图 */ case AN: return CreateAN(G); /* 构造无向网 */ default: return ERROR; } } void DestroyGraph(MGraph *G) { /* 初始条件: 图G存在。操作结果: 销毁图G */ int i,j; if((*G).kind<2) /* 有向 */ for(i=0;i<(*G).vexnum;i++) /* 释放弧的相关信息(如果有的话) */ { for(j=0;j<(*G).vexnum;j++) if((*G).arcs[i][j].adj==1&&(*G).kind==0||(*G).arcs[i][j].adj!=INFINITY&&(*G).kind==1) /* 有向图的弧||有向网的弧 */ if((*G).arcs[i][j].info) /* 有相关信息 */ { free((*G).arcs[i][j].info); (*G).arcs[i][j].info=NULL; } } else /* 无向 */ for(i=0;i<(*G).vexnum;i++) /* 释放边的相关信息(如果有的话) */ for(j=i+1;j<(*G).vexnum;j++) if((*G).arcs[i][j].adj==1&&(*G).kind==2||(*G).arcs[i][j].adj!=INFINITY&&(*G).kind==3) /* 无向图的边||无向网的边 */ if((*G).arcs[i][j].info) /* 有相关信息 */ { free((*G).arcs[i][j].info); (*G).arcs[i][j].info=(*G).arcs[j][i].info=NULL; } (*G).vexnum=0; (*G).arcnum=0; } VertexType* GetVex(MGraph G,int v) { /* 初始条件: 图G存在，v是G中某个顶点的序号。操作结果: 返回v的值 */ if(v>=G.vexnum||v<0) exit(ERROR); return &G.vexs[v]; } Status PutVex(MGraph *G,VertexType v,VertexType value) { /* 初始条件: 图G存在，v是G中某个顶点。操作结果: 对v赋新值value */ int k; k=LocateVex(*G,v); /* k为顶点v在图G中的