数据结构课程设计题目02599(2).docx

《数据结构课程设计题目02599(2).docx》由会员分享，可在线阅读，更多相关《数据结构课程设计题目02599(2).docx（6页珍藏版）》请在第一文库网上搜索。

1、printf(%8s,g-adj1isti.vertex);for(i=0;in;i+)printf(%8s,g-adj1isti.vertex);for(j=On+)printf(,%9d,aij);Printfrn)；)遍历子模块/*/*函数名：dfs_main*/*函数功能：生成导游线路图*/*入口参数：g-景点分布图*/*g1导游线路图*/*返回值：无*/*/voiddfs_main(1graph*g,1graph*g1)(intvisitedMAX_VERTEX_NUM;intx,i;intvexMAX_VERTEX_NUM;intj,k,i1,tag;intvex1MAX_VERT

2、EX_NUM;Edge_node*p,*q;for(i=0;in=0)Printf(景点分布图未输入，无法生成导游线图！n);return;)doPrimfr请输入口景点序号：)；scanf(%d,=1&xn)break;)e1sePrintf(景点号输入有误，请重新输入！n);Jwhi1e(I);j=0;dfs(g,x,visited,vex,&j)J/每次调用时，j初始化为0/*构建游览线路，存放在数组Vex1*/i1=0;fdr(i=O;in-1;i+)(j=vexi+1;tag=1;k=0;whi1e(tag)(vex1i1+=vexi+k;p=g-adj1istvexi+k.firs

3、tedge;whi1e(p!=NU11&p-adjvex!=j)/*判断vik与vj之间有没有边*/p=p-next;if(P=NU11)k;/*若vi+k与vj之间没有边回溯*/e1setag=O;1)vex1i1+=j;/*建立游览线路图的邻接链表G1,供拓朴排序用*/for(i=0;in;i+)(strcpy(g1-adj1isti.vertex,g-adj1isti.vertex);g1-adjIisti.firstedge=NU11;for(k=O;kadjvex=j;p-weight=1;/*建立游览线路图时，不考虑边的权值*/q=g1-adj1isti.firstedge;g1-

4、adj1isti.firstedge=p;p-next=q;)g1-n=g-n;g1-m=i1-1;/*输出游览线路*/Printf(“游览线路为n：)；for(k=O;k,g-adj1isti.vertex);)printf(tt%sn,g-adj1istvex1i1-1.vertex);*函数名：dfs*/*函数功能：以Vi为出发点对邻接表存储的图G进行DFS搜索*/*入口参数：g-图G的邻接表存储*/*i-顶点Vi*/*visited-标志顶点是否己被访问的数组*/*vex一存放遍历时所经过的顶点*/*j-存放位置*/*返回值：无*/*/voiddfs(1graph*g,inti,int

5、visited,intvex.int*j)(intk;staticj=0;Edgejode*p;printf(visitVer1ex:V%sn”,g-adj1isi.vertex);/*访问顶点Vi*/vex*j=i;/*遍历结点vi,存入数组Vex中*/*j=*j+1;ViSitedi=1;/*标记Vi已访问*/p=g-adj1isti.firstedge*BXVi边表的头指针*/whi1e(p)/*依次搜索Vi的邻接点Vj,j=p-adjva*/(k=p-adjvex;if(!visitedk)/*若Vj尚未访问，则以Vj为出发点向纵深搜索*/dfs(g,k,visited,vex,j);

6、p=pnext;/水找Vi的下一个邻接点*/)在本任务中，通过10.4节的遍历输出景区旅游导游线路，该线路从入口出发，经过所有旅游景点后到达出口。在输出的导游线图中，有可能出现回路，即一个景点经过两次及两次以上。为了实现导游线路图的优化，首先要判断图中有没有回路，若有，回路由哪几个景点组成。然后尽可能消除回路。比如说可以通过景区之间多修建道路来消除回路。当然，如果确实存在困难，不能彻底消除回路,也最好使回路经过的景点最少。其中，判断导游线路图有无回路，可用拓朴排序来解决，若有回路则输出回路中的景点。要实现这一功能，可直接使用上述程序，存在回路时，输出未能拓朴排序的顶点。main()(1grap

7、h*g;intvexMAX_VERTEX_NUM,aMAX_VERTEX_NUMMAX_VERTEX_NUM,vexnoMAX_VERTEX_NUM;intij,n,k;Edge_node*p;for(i=0;in;for(i=O;in;i+)fbr(j=O;jn;j+)aij=O;for(i=0;iadj1isti.firstcdge;whi1e(p!=NU11)(j=p-adjvex;aij=p-weight;p=p-next;)for(i=0;in;i+)vexnoi=i;k=topo_sort(a,vex,vexno,n);if(k=O)(Printfr该图有回路，回路中的景点为：W);for(i=0;iadj1istvexi.vertex);1)e1sePrintf(“该图没有回路);)1.1.5运行测试