资源描述：
《图的深度优先遍历算法课程设计报告》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、课程设计报告2013〜2014学年第二学期课程数据结构与算法课程设计名称图的深度优先遍历算法的实现学生姓名陈琳学号1204091022专业班级软件工程指导教师何立新2014年9月一：问题分析和任务定义涉及到数据结构遍会涉及到对应存储方法的遍历问题。本次程序采用邻接表的存储方法，并且以深度优先实现遍历的过程得到其遍历序列。深度优先遍历图的方法是，从图屮某顶点V出发：(1)访问顶点V;(2)依次从v的未被访问的邻接点出发，对图进行深度优先遍历；直至图屮和v有路径相通的顶点都被访问；(3)若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直
2、到图中所有顶点均被访问过为止。二：数据结构的选择和概要设计设计流程如图：建接创邻表建创图S又殳历深优遍阁1设计流程利用一维数组创建邻接表，同时还需要一个一维数组来存储顶点信息。之后利用创建的邻接表来创建图，最后用深度优先的方法來实现遍历。深度优先遍历是连通图的一种遍历策略。其基本思想如下：设X是当前被访问顶点，在对X做过访问标记后，选择一条从X出发的未检测过的边(X，y)。若发现顶点y已访问过，则重新选择另一条从x出发的未检测过的边，否则沿边(X，y)到达未曾访问过的y,对y访问并将其标记为己访问过；然后从y开始搜索，直到搜索完从y出发的所有路径，即访问完所有从
3、y出发可达的顶点之后，才回溯到顶点x,并且再选择一条从x出发的未检测过的边。上述过程直至从x出发的所有边都已检测过为止。例如下阁屮(既本次设计用到的阁).•1.从0幵始，首先找到0的关联顶点32.由3出发，找到1;由1出发，没有关联的顶点。3.回到3,从3岀发，找到2;由2出发，没有关联的顶点。4.回到4，出4出发，找到1，因为1己经被访问过了，所以不访问。所以最后顺序是0,3,1,2,4三：详细设计和编码1.创建邻接表和图voidGreatcALGraph(ALGraph*G)//建立邻接表函数.{inti,j,k,s;chary;EdgeNode*p;//工
4、作指针.printf("请输入图的顶点数n与边数e(以逗号做分隔符)：rf);scanf(〃％d,%d"，&(G->n),&(G-〉e));scanf&y);//用y来接收回车符.for(s=0;s〈G-〉n;s++){printf("请输入下标为%d的顶点的元素:"，s);scanf("%c〃,&(G-〉adjlist[s].vertex));scanf("%c"，&y);//用y来接收回车符.当后而要输入的是和单个字符有关的数据时候要存贮回车符，以免回车符被误接收。G->adjlist[s].firstedge=NULL;}printf("请分别输入该
5、图的%(;1条弧",G->e);for(k=0;k〈G->e;k++){printfC请输入第%(1条弧的起点和终点(起点下标，终点下标):'(k+1));scanf("%d，％d"，&i,&j);p=(EdgeNode*)malloc(sizeof(EdgeNode));p->adjvex=j;p->next=G->adjlist[i].firstedge;G->adjlist[i].firstedge=p;}}2.深度优先遍历voidDFS(ALGraph*G,intv)//深度优先遍历{EdgeNode*p;intw;printf("%c",G->
6、adjlist[v].vertex);visited[v]=True;for(p=G->adjlist[v].firstedge;p;p=p->noxt){v=p->adjvex;if(!visitedW)DFS(G,w);//对于没有访问过的顶点，调用深度优先搜索函数}}voidDEStravorse(ALGraph*G){intv;for(v=0;vn;v++){visitod[v]=Ealso;}for(v=0;vn;v++)//对v尚未访问到的邻接点w进行一个递归遍历.{if(!visited[v])DES(G,v);}四：上机调试过程
7、C2018：unknowncharacter'0xd6'C2018:unknowncharacter'0xd5'C2018：unknowncharacter'0xb5'C2018：unknowncharacter'0xe3'C2018:unknowncharacter'Oxcf'在创建图时，输入程序printf("第%d条弧的起点和终点(格式为"起点下标，终点下标):",(kH));运行发现有十六个错误，错误截图为：C:UsersAdministratorDesktop2.c(61):errorC:UsersAdministratorDeskt
8、op2.c(61):e
