校园导游系统数据结构图..docVIP

西安郵電學院 目： 校 园 导 游 系 统 院系名称： 计 算 机 学 院 专业名称： 计算机科学与技术 班 级： 1006 学生姓名： **** 学号（8位）：***** 指导教师： ****** 设计起止时间：2011年月日~20年月日MGraph型，G-vexnum表示顶点的个数；G-arcnum表示边数。CreatUDN()函数的功能就是实现图的创建，将已知的景点的一些信息，转换成图的信息，并进行存储。 三．详细设计（主要函数的程序流程图） 1.任意两个地点之间的一条最短（中转最少）的简单路径 利用遍历的思想，遍历图找出一条最佳最佳的的路径，让它遍历所有景点。往下遍历，访问标志位，若访问过在下次就不用访问。若找完一个分支在下次重新遍历。 zz[0]-zhi=m; zz[0]-front=NULL; flag[m]=1; for(top=0;top20;top++) { for(i=0;i20;i++) { if(G-arcs[zz[top]-zhi][i].adj!=INFINITYi==n) { printf(%s\n,G-vexs[n].name); printf(%s\n,G-vexs[zz[top]-zhi].name); zz[top]=zz[top]-front; while(zz[top]!=NULL) { printf(%s\n,G-vexs[zz[top]-zhi].name); zz[top]=zz[top]-front; } getch(); return; } else if(G-arcs[zz[top]-zhi][i].adj!=INFINITYflag[i]==0) { zz[++j]-zhi=i; zz[j]-front=zz[top]; flag[i]=1; } } } 2.任意两个景点的最佳访问路线（带权）查询 利用迪杰特斯拉算法，求v0到其余顶点的最短路径D[],p [][]是用来存放各路径的权值，借助辅助数组final[]标志,是否当前顶点属于final(1,属于)。 for(v=0;vG-vexnum;v++) { final[v]=0; D[v]=G-arcs[v0][v].adj; for(w=0;wG-vexnum;w++) p[v][w]=0; if(D[v]INFINITY) { p[v][v0]=1;p[v][v]=1; } } D[v0]=0;final[v0]=1; for(i=1;iG-vexnum;i++) { min=INFINITY; for(w=0;wG-vexnum;w++) if(!final[w]) if(D[w]min){v=w;min=D[w];} final[v]=1; for(w=0;wG-vexnum;w++) if(!final[w](min+G-arcs[v][w].adjD[w])) { D[w]=min+G-arcs[v][w].adj; for(x=0;xG-vexnum;x++) p[w][x]=p[v][x]; p[w][w]=1; } } v=v1; w1=v0; printf(%s,G-vexs[v0].name); do { flag=0;min=INFINITY; for(w=0;wG-vexnum;w++) { if(p[v][w]w!=v0) { flag=1; if(D[w]min) { j=w; min=D[w]; } } } 3.任意两个地点之间的所有路径 利用深度优先的思想，遍历图找出所有的路径，让它遍历所有景点。利用递归的思想，往下历，访问标志位，若访问过在下次就不用访问。{ int s; if(v[k]==j)/*找到一条路径*/ { count++;/*路径的条数值加1*/ printf(第%d条:,count); for(s=1;sk;s++)/*输出一条路径*/ printf(%s-,G-vexs[v[s]].name); printf(%s\n,G-vexs[v[s]].name); } for(s = 1;sG-vexnum;s++) { if(s!=i)/*保证找到的是简单路径*/ {