圖的深度優(yōu)先遍歷算法課程設(shè)計(jì)報(bào)告

合肥學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系課程設(shè)計(jì)報(bào)告2023～2023學(xué)年第二學(xué)期課程數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)名稱圖的深度優(yōu)先遍歷算法的實(shí)現(xiàn)學(xué)生姓名陳琳學(xué)號1204091022專業(yè)班級軟件工程指導(dǎo)教師何立新2023年9月一：問題分析和任務(wù)定義涉及到數(shù)據(jù)結(jié)構(gòu)遍會涉及到對應(yīng)存儲方法的遍歷問題。本次程序采用鄰接表的存儲方法，并且以深度優(yōu)先實(shí)現(xiàn)遍歷的過程得到其遍歷序列。深度優(yōu)先遍歷圖的方法是，從圖中某頂點(diǎn)v出發(fā)：〔1〕訪問頂點(diǎn)v；〔2〕依次從v的未被訪問的鄰接點(diǎn)出發(fā)，對圖進(jìn)行深度優(yōu)先遍歷；直至圖中和v有路徑相通的頂點(diǎn)都被訪問；〔3〕假設(shè)此時(shí)圖中尚有頂點(diǎn)未被訪問，那么從一個(gè)未被訪問的頂點(diǎn)出發(fā)，重新進(jìn)行深度優(yōu)先遍歷，直到圖中所有頂點(diǎn)均被訪問過為止。二：數(shù)據(jù)結(jié)構(gòu)的選擇和概要設(shè)計(jì)設(shè)計(jì)流程如圖：深度優(yōu)先遍歷深度優(yōu)先遍歷創(chuàng)立鄰接表創(chuàng)立圖創(chuàng)立鄰接表創(chuàng)立圖圖1設(shè)計(jì)流程利用一維數(shù)組創(chuàng)立鄰接表，同時(shí)還需要一個(gè)一維數(shù)組來存儲頂點(diǎn)信息。之后利用創(chuàng)立的鄰接表來創(chuàng)立圖，最后用深度優(yōu)先的方法來實(shí)現(xiàn)遍歷。深度優(yōu)先遍歷是連通圖的一種遍歷策略。其根本思想如下：設(shè)x是當(dāng)前被訪問頂點(diǎn)，在對x做過訪問標(biāo)記后，選擇一條從x出發(fā)的未檢測過的邊(x，y)。假設(shè)發(fā)現(xiàn)頂點(diǎn)y已訪問過，那么重新選擇另一條從x出發(fā)的未檢測過的邊，否那么沿邊(x，y)到達(dá)未曾訪問過的y，對y訪問并將其標(biāo)記為已訪問過；然后從y開始搜索，直到搜索完從y出發(fā)的所有路徑，即訪問完所有從y出發(fā)可達(dá)的頂點(diǎn)之后，才回溯到頂點(diǎn)x，并且再選擇一條從x出發(fā)的未檢測過的邊。上述過程直至從x出發(fā)的所有邊都已檢測過為止。例如下列圖中〔既本次設(shè)計(jì)用到的圖〕：0012412433圖2原始圖1.從0開始，首先找到0的關(guān)聯(lián)頂點(diǎn)32.由3出發(fā)，找到1；由1出發(fā)，沒有關(guān)聯(lián)的頂點(diǎn)。3.回到3，從3出發(fā)，找到2；由2出發(fā)，沒有關(guān)聯(lián)的頂點(diǎn)。4.回到4，出4出發(fā)，找到1，因?yàn)?已經(jīng)被訪問過了，所以不訪問。所以最后順序是0,3,1,2,4三：詳細(xì)設(shè)計(jì)和編碼創(chuàng)立鄰接表和圖voidCreateALGraph(ALGraph*G)//建立鄰接表函數(shù).{inti,j,k,s; chary;EdgeNode*p;//工作指針. printf("請輸入圖的頂點(diǎn)數(shù)n與邊數(shù)e(以逗號做分隔符)：\n"); scanf("%d,%d",&(G->n),&(G->e)); scanf("%c",&y);//用y來接收回車符. for(s=0;s<G->n;s++) { printf("請輸入下標(biāo)為%d的頂點(diǎn)的元素:\n",s); scanf("%c",&(G->adjlist[s].vertex)); scanf("%c",&y);//用y來接收回車符.當(dāng)后面要輸入的是和單個(gè)字符有關(guān)的數(shù)據(jù)時(shí)候要存貯回車符，以免回車符被誤接收。 G->adjlist[s].firstedge=NULL; } printf("請分別輸入該圖的%d條弧\n",G->e); for(k=0;k<G->e;k++) { printf("請輸入第%d條弧的起點(diǎn)和終點(diǎn)〔起點(diǎn)下標(biāo),終點(diǎn)下標(biāo)〕:\n",(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; }}深度優(yōu)先遍歷voidDFS(ALGraph*G,intv)//深度優(yōu)先遍歷{EdgeNode*p; intw; printf("%c",G->adjlist[v].vertex); visited[v]=True; for(p=G->adjlist[v].firstedge;p;p=p->next) { w=p->adjvex; if(!visited[w]) DFS(G,w);//對于沒有訪問過的頂點(diǎn)，調(diào)用深度優(yōu)先搜索函數(shù) }}voidDFStraverse(ALGraph*G){intv; for(v=0;v<G->n;v++) { visited[v]=False; } for(v=0;v<G->n;v++)//對v尚未訪問到的鄰接點(diǎn)w進(jìn)行一個(gè)遞歸遍歷. { if(!visited[v]) DFS(G,v); }}四：上機(jī)調(diào)試過程在創(chuàng)立圖時(shí)，輸入程序printf("第%d條弧的起點(diǎn)和終點(diǎn)〔格式為"起點(diǎn)下標(biāo),終點(diǎn)下標(biāo)"〕:\n",(k+1));運(yùn)行發(fā)現(xiàn)有十六個(gè)錯(cuò)誤，錯(cuò)誤截圖為：圖3調(diào)試錯(cuò)誤圖經(jīng)調(diào)試，將該段程序修改為：printf("請輸入第%d條弧的起點(diǎn)和終點(diǎn)〔起點(diǎn)下標(biāo),終點(diǎn)下標(biāo)〕:\n",(k+1));即可成功。五：測試結(jié)果及其分析1.測試結(jié)果：圖4測試結(jié)果圖2.分析此程序的圖如下：0031243124圖5原始圖遍歷從0開始，第一步到30031243124圖6第一次遍歷與3相連的有1和2，在此先遍歷10031243124圖7第二次遍歷而與1相關(guān)的沒有，那么返回到3，與3相連的有1和2，1遍歷過，所以遍歷20031243124圖8第三次遍歷2沒有與之相關(guān)的頂點(diǎn)返回3,3的所有相關(guān)都遍歷過，返回0，只剩下40031243124圖9第四次遍歷與4相關(guān)的1已遍歷過，返回0,0的所有相關(guān)都已遍歷，那么深度優(yōu)先遍歷結(jié)束。遍歷順序：03124六：用戶使用說明1.根據(jù)屏幕提示輸入圖的頂點(diǎn)數(shù)n與邊數(shù)e(以逗號做分隔符)；2.依次輸入下標(biāo)為0,1,2……〔n-1〕的頂點(diǎn)的元素；3.依次輸入第1,2……e條弧的起點(diǎn)和終點(diǎn)，格式為：起點(diǎn)下標(biāo)，終點(diǎn)下標(biāo)；4.即可得出所輸入圖的深度優(yōu)先遍歷序列；七：參考文獻(xiàn)1.王昆侖、李紅.《數(shù)據(jù)結(jié)構(gòu)與算法〔第二版〕》.北京：中國鐵道出版社，20232.程杰.《大話數(shù)據(jù)結(jié)構(gòu)[M]》.北京:清華大學(xué)出版社，20233.韓利凱、李軍.《數(shù)據(jù)結(jié)構(gòu)[M]》.浙江:浙江大學(xué)出版社，20234.謝假設(shè)陽.《數(shù)據(jù)結(jié)構(gòu)[M].北京》：清華大學(xué)出版社，20235.黃國瑜、葉乃菁.《數(shù)據(jù)結(jié)構(gòu)[M]》.北京：清華大學(xué)出版社，2023八：附錄//以鄰接表為存儲結(jié)構(gòu)的深度優(yōu)先搜索算法#include"stdio.h"#include"malloc.h"#defineMaxVerNum8#defineMAXSIZE100//頂點(diǎn)最大個(gè)數(shù)#defineFalse0#defineTrue1intvisited[MaxVerNum];//全局變量，0表示未被訪問過，1表示已被訪問過typedefcharVertexType;typedefstructnode//鄰接表節(jié)點(diǎn).{intadjvex;//鄰接點(diǎn)的位置structnode*next;//指向下一個(gè)節(jié)點(diǎn)}EdgeNode;//鄰接表中的節(jié)點(diǎn)類型typedefstructvnode//頂點(diǎn)節(jié)點(diǎn).{VertexTypevertex;//頂點(diǎn)信息EdgeNode*firstedge;//指向第一個(gè)鄰接表節(jié)點(diǎn)}VertexNode;//表頭節(jié)點(diǎn)類型typedefstruct{VertexNodeadjlist[MaxVerNum];//存儲鄰接表節(jié)點(diǎn)的一維數(shù)組intn,e;//定義頂點(diǎn)數(shù)n和邊數(shù)e}ALGraph;//鄰接表類型voidCreateALGraph(ALGraph*G)//建立鄰接表函數(shù).{inti,j,k,s;chary;EdgeNode*p;//工作指針.printf("請輸入圖的頂點(diǎn)數(shù)n與邊數(shù)e(以逗號做分隔符)：\n");scanf("%d,%d",&(G->n),&(G->e));scanf("%c",&y);//用y來接收回車符.for(s=0;s<G->n;s++){printf(“請輸入下標(biāo)為%d的頂點(diǎn)的元素:\n",s);scanf("%c",&(G->adjlist[s].vertex));scanf("%c",&y);//用y來接收回車符.當(dāng)后面要輸入的是和單個(gè)字符有關(guān)的數(shù)據(jù)時(shí)候要存貯回車符，以免回車符被誤接收。G->adjlist[s].firstedge=NULL;}printf("請分別輸入該圖的%d條弧\n",G->e); for(k=0;k<G->e;k++){printf("請輸入第%d條弧的起點(diǎn)和終點(diǎn)〔起點(diǎn)下標(biāo),終點(diǎn)下標(biāo)〕:\n",(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;}}voidDFS(ALGraph*G,intv)//深度優(yōu)先遍歷{EdgeNode*p;intw;printf("%c",G->adjlist[v].vertex); visited[v]=True; for(p=G->adjlist[v].firstedge;p;p=p->next) w=p->adjvex; if(!visited[w]) DFS(G,w);//對于沒有訪問過的頂點(diǎn)，調(diào)用深度優(yōu)先搜索函數(shù)}}voidDFStraverse(ALGraph*G){intv; for(v=0;v<G->n;v++){ visited[v]=False;}for(v=0;v<G->n;v