數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告九-圖的遍歷

問題描述：若用有向網(wǎng)表示網(wǎng)頁的鏈接網(wǎng)絡(luò)，其中頂點(diǎn)表示某個網(wǎng)頁，有向弧表示網(wǎng)頁之間的鏈接關(guān)系。試設(shè)計(jì)一個網(wǎng)絡(luò)蜘蛛系統(tǒng)，分別以廣度優(yōu)先和深度優(yōu)先的策略抓取網(wǎng)頁。需求分析：本程序要求采用利用圖實(shí)現(xiàn)廣度優(yōu)先搜索。首先輸入頂點(diǎn)的數(shù)量，然后是各頂點(diǎn)對應(yīng)的字母，再輸入各條?。?quán)值都置為1）。在Dos界面輸出從首個頂點(diǎn)開始的廣度優(yōu)先遍歷序列。測試數(shù)據(jù) 輸入輸入頂點(diǎn)數(shù)和弧數(shù):89輸入8個頂點(diǎn).輸入頂點(diǎn)0:a輸入頂點(diǎn)1:b輸入頂點(diǎn)2:c輸入頂點(diǎn)3:d輸入頂點(diǎn)4:e輸入頂點(diǎn)5:f輸入頂點(diǎn)6:g輸入頂點(diǎn)7:h輸入9條弧.輸入弧0:ab1輸入弧1:bd1輸入弧2:be1輸入弧3:dh1輸入弧4:eh1輸入弧5:ac1輸入弧6:cf1輸入弧7:cg1輸入弧8:fg1輸出廣度優(yōu)先遍歷:abdhecfg深度優(yōu)先遍歷:abcdefgh二、概要設(shè)計(jì)：抽象數(shù)據(jù)類型：圖的定義：ADTGraph

{

數(shù)據(jù)對象V：V是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點(diǎn)集。

數(shù)據(jù)關(guān)系R：R={VR}VR={<v,w>|v,w∈v且P(v,w),<v,w>表示從v到w的弧，謂詞P(v,w)定義了弧<v,w>的意義或信息}

基本操作P：CreateGraph(&G,V,VR)初始條件：V是圖的頂點(diǎn)集，VR是圖中弧的集合

操作結(jié)果：按V和VR的定義構(gòu)造圖GFirstAdjVex(G,v)初始條件：圖G存在,v是G中某個頂點(diǎn)操作結(jié)果：返回v的第一個鄰接頂點(diǎn)，若頂點(diǎn)在G中沒有鄰接頂點(diǎn)，則返回“空”NextAdjVex(G,v,w)初始條件：圖G存在，v是G中某個頂點(diǎn)，w是v的鄰接頂點(diǎn)操作結(jié)果：返回v的（相對于w的）下一個鄰接頂點(diǎn)，若w是v的最后一個鄰接點(diǎn)，則返回“空”visit(G,k)初始條件：圖G存在操作結(jié)果：訪問圖G中的第K個節(jié)點(diǎn)Locate(G,c)初始條件：圖G存在操作結(jié)果：訪問圖G中的c頂點(diǎn)DFS(G,v)初始條件：圖G存在操作結(jié)果：以圖G中的第v個節(jié)點(diǎn)為起點(diǎn)深度優(yōu)先訪問圖GBFS(G)初始條件：圖G存在操作結(jié)果：廣度優(yōu)先訪問圖G

}ADTGraph算法的基本思想：（1）圖的特點(diǎn)是沒有首尾之分，所以算法的參數(shù)要指定訪問的第一個頂點(diǎn)。（2）對圖的遍歷路徑有可能構(gòu)成一個回路，從而造成死循環(huán)，所以算法設(shè)計(jì)要考慮遍歷路徑可能出現(xiàn)的死循環(huán)問題。（3）一個頂點(diǎn)可能和若干個頂點(diǎn)都是鄰接頂點(diǎn)，要使一個頂點(diǎn)的所有鄰接頂點(diǎn)按照某種次序被訪問。深度優(yōu)先搜索遍歷連通圖的深度優(yōu)先遍歷遞歸算法可描述為：（1）訪問頂點(diǎn)vi并標(biāo)記頂點(diǎn)vi為已訪問；（2）查找頂點(diǎn)v的第一個鄰接頂點(diǎn)vj；（3）若頂點(diǎn)v的鄰接頂點(diǎn)vj存在，則繼續(xù)執(zhí)行，否則算法結(jié)束；（4）若頂點(diǎn)vj尚未被訪問，則深度優(yōu)先遍歷遞歸訪問頂點(diǎn)vj；（5）查找頂點(diǎn)vi的鄰接頂點(diǎn)vj的下一個鄰接頂點(diǎn)，轉(zhuǎn)到步驟（3）。當(dāng)尋找頂點(diǎn)vi的鄰接頂點(diǎn)vj成功時繼續(xù)進(jìn)行，當(dāng)尋找頂點(diǎn)vi的鄰接頂點(diǎn)vj失敗時回溯到上一次遞歸調(diào)用的地方繼續(xù)進(jìn)行。為了在遍歷過程中便于區(qū)分頂點(diǎn)是否被訪問，需附設(shè)訪問標(biāo)志數(shù)組visited[]，其初值為0，一旦某個頂點(diǎn)被訪問，則其相應(yīng)的分量置為1。廣度優(yōu)先遍歷算法： 需要一個隊(duì)列以保持訪問過的頂點(diǎn)的順序，以便按順序訪問這些頂點(diǎn)鄰接頂點(diǎn)。連通圖的廣度優(yōu)先遍歷算法為：（1）訪問初始頂點(diǎn)v并標(biāo)記頂點(diǎn)v為已訪問；（2）頂點(diǎn)v入隊(duì)列；（3）當(dāng)隊(duì)列非空時則繼續(xù)執(zhí)行，否則算法結(jié)束；（4）出隊(duì)列取得隊(duì)頭頂點(diǎn)u；（5）查找頂點(diǎn)u的第一個鄰接頂點(diǎn)w；（6）若頂點(diǎn)u的鄰接頂點(diǎn)w不存在，則轉(zhuǎn)到步驟（3），否則執(zhí)行后序語句：①若頂點(diǎn)w尚未被訪問，則訪問頂點(diǎn)w并標(biāo)記頂點(diǎn)w為已訪問；②頂點(diǎn)w入隊(duì)列；③查找頂點(diǎn)u的鄰接頂點(diǎn)w后的下一個鄰接頂點(diǎn)，轉(zhuǎn)到步驟（6）。程序的流程程序由三個模塊組成：（1）主程序模塊：包括圖的創(chuàng)建，鄰接點(diǎn)的查找和頂點(diǎn)的查找（2）數(shù)據(jù)保存中間變量模塊：實(shí)現(xiàn)用數(shù)組代替隊(duì)列存?。?）元素結(jié)構(gòu)單元模塊：定義圖每個元素的結(jié)構(gòu)三、詳細(xì)設(shè)計(jì)1．元素類型，圖類型typedefstruct{char*vexs;//頂點(diǎn)向量intarcs[MAX_VEX][MAX_VEX];//鄰接矩陣intvexnum,arcnum;//圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)}Graph,*GP;2．根據(jù)圖的特點(diǎn)，G即為該圖的名稱，該程序的基本操作具體實(shí)現(xiàn)如下voidEnQueue(inte){base[rear]=e;rear=(rear+1)%QUEUE_SIZE;}voidDeQueue(int&e){e=base[front];front=(front+1)%QUEUE_SIZE;}public:int*base;intfront;intrear;};//圖G中查找元素c的位置intLocate(GraphG,charc){for(inti=0;i<G.vexnum;i++)if(G.vexs[i]==c)returni;return-1;}//創(chuàng)建無向網(wǎng)voidCreateUDN(Graph&G){inti,j,w,s1,s2;chara,b,temp;cout<<"輸入頂點(diǎn)數(shù)和弧數(shù):";cin>>G.vexnum>>G.arcnum;temp=getchar();//接收回車G.vexs=(char*)malloc(G.vexnum*sizeof(char));//分配頂點(diǎn)數(shù)目cout<<"輸入頂點(diǎn)："<<endl;for(i=0;i<G.vexnum;i++){//初始化頂點(diǎn) cout<<"輸入頂點(diǎn)"<<i<<":";cin>>G.vexs[i];temp=getchar();//接收回車}for(i=0;i<G.vexnum;i++)//初始化鄰接矩陣for(j=0;j<G.vexnum;j++)G.arcs[i][j]=INFINITY;cout<<"輸入弧:"<<endl;for(i=0;i<G.arcnum;i++){//初始化弧cout<<"輸入弧"<<i<<":";cin>>a>>b>>w;//輸入一條邊依附的頂點(diǎn)和權(quán)值temp=getchar();//接收回車s1=Locate(G,a);s2=Locate(G,b);G.arcs[s1][s2]=G.arcs[s2][s1]=w;}}//圖G中頂點(diǎn)k的第一個鄰接頂點(diǎn)intFirstVex(GraphG,intk){if(k>=0&&k<G.vexnum){//k合理for(inti=0;i<G.vexnum;i++)if(G.arcs[k][i]!=INFINITY)returni;}return-1;}//圖G中頂點(diǎn)i的第j個鄰接頂點(diǎn)的下一個鄰接頂點(diǎn)intNextVex(GraphG,inti,intj){if(i>=0&&i<G.vexnum&&j>=0&&j<G.vexnum){//i,j合理for(intk=j+1;k<G.vexnum;k++)if(G.arcs[i][k]!=INFINITY)returnk;}return-1;}//深度優(yōu)先遍歷voidDFS(GraphG,intk){inti;if(k==-1){//第一次執(zhí)行DFS時,k為-1for(i=0;i<G.vexnum;i++)if(!visited[i])DFS(G,i);//對尚未訪問的頂點(diǎn)調(diào)用DFS}else{visited[k]=true;cout<<G.vexs[k];//訪問第k個頂點(diǎn)for(i=FirstVex(G,k);i>=0;i=NextVex(G,k,i))if(!visited[i])DFS(G,i);//對k的尚未訪問的鄰接頂點(diǎn)i遞歸調(diào)用DFS}}//廣度優(yōu)先遍歷voidBFS(GraphG){intk;QueueQ;//輔助隊(duì)列QQ.InitQueue();for(inti=0;i<G.vexnum;i++)if(!visited[i]){//i尚未訪問visited[i]=true;cout<<G.vexs[i];Q.EnQueue(i);//i入列while(Q.front!=Q.rear){Q.DeQueue(k);//隊(duì)頭元素出列并置為kfor(intw=FirstVex(G,k);w>=0;w=NextVex(G,k,w))if(!visited[w]){//w為k的尚未訪問的鄰接頂點(diǎn)visited[w]=true;cout<<G.vexs[w];Q.EnQueue(w);}}}}3．主程序中，直接調(diào)用main函數(shù)其大概流程圖為，具體代碼實(shí)現(xiàn)如下：voidmain(){inti;GraphG;CreateUDN(G);visited=(bool*)malloc(G.vexnum*sizeof(bool));cout<<"廣度優(yōu)先遍歷:";for(i=0;i<G.vexnum;i++)visited[i]=false;DFS(G,-1);cout<<endl;cout<<"深度優(yōu)先遍歷:";for(i=0;i<G.vexnum;i++)visited[i]=false;BFS(G);cout<<endl;}算法的時空分析:對于具有n個頂點(diǎn)e條邊的無向圖，當(dāng)圖采用鄰接矩陣存儲時，BFS算法的總時間為O（）。輸入和輸出的格式： 輸入：輸入定點(diǎn)數(shù)和弧數(shù)：mn輸入定點(diǎn)：輸入弧：輸出：廣度優(yōu)先遍歷：深度優(yōu)先遍歷：四、調(diào)試分析略。五、測試結(jié)果本實(shí)驗(yàn)的測試結(jié)果截圖如下：分析：如右圖所示六、用戶使用說明（可選）1、本程序的運(yùn)行環(huán)境為windows操作系統(tǒng)，執(zhí)行文件為tu.exe2、運(yùn)行程序時提示輸入數(shù)據(jù)并且輸入數(shù)據(jù)然后回車就可以繼續(xù)輸入相應(yīng)數(shù)據(jù)，最后即可得到結(jié)果。七、實(shí)驗(yàn)心得（可選）本次實(shí)驗(yàn)設(shè)計(jì)內(nèi)容比較多，雖然實(shí)驗(yàn)過程中多次出現(xiàn)問題，但通過多次調(diào)試最終得到解決。并且通過本次試驗(yàn)，對圖的建立有了更深入的了解，對書上的代碼進(jìn)行了實(shí)現(xiàn)，熟悉并掌握了BFS、DFS算法，以及圖的兩種存儲結(jié)構(gòu)，對圖結(jié)構(gòu)的計(jì)算與運(yùn)用有了進(jìn)一步的體會。附錄（實(shí)驗(yàn)代碼）：#include<iostream>#defineINFINITY32767#defineMAX_VEX20//最大頂點(diǎn)個數(shù)#defineQUEUE_SIZE(MAX_VEX+1)//隊(duì)列長度usingnamespacestd;bool*visited;//訪問標(biāo)志數(shù)組//圖的鄰接矩陣存儲結(jié)構(gòu)typedefstruct{char*vexs;//頂點(diǎn)向量intarcs[MAX_VEX][MAX_VEX];//鄰接矩陣intvexnum,arcnum;//圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)}Graph;//隊(duì)列類classQueue{public:voidInitQueue(){base=(int*)malloc(QUEUE_SIZE*sizeof(int));front=rear=0;}voidEnQueue(inte){base[rear]=e;rear=(rear+1)%QUEUE_SIZE;}voidDeQueue(int&e){e=base[front];front=(front+1)%QUEUE_SIZE;}public:int*base;intfront;intrear;};//圖G中查找元素c的位置intLocate(GraphG,charc){for(inti=0;i<G.vexnum;i++)if(G.vexs[i]==c)returni;return-1;}//創(chuàng)建無向網(wǎng)voidCreateUDN(Graph&G){inti,j,w,s1,s2;chara,b,temp;cout<<"輸入頂點(diǎn)數(shù)和弧數(shù):";cin>>G.vexnum>>G.arcnum;temp=getchar();//接收回車G.vexs=(char*)malloc(G.vexnum*sizeof(char));//分配頂點(diǎn)數(shù)目cout<<"輸入頂點(diǎn)："<<endl;for(i=0;i<G.vexnum;i++){//初始化頂點(diǎn) cout<<"輸入頂點(diǎn)"<<i<<":";cin>>G.vexs[i];temp=getchar();//接收回車}for(i=0;i<G.vexnum;i++)//初始化鄰接矩陣for(j=0;j<G.vexnum;j++)G.arcs[i][j]=INFINITY;cout<<"輸入弧:"<<endl;for(i=0;i<G.arcnum;i++){//初始化弧cout<<"輸入弧"<<i<<":";cin>>a>>b>>w;//輸入一條邊依附的頂點(diǎn)和權(quán)值temp=getchar();//接收回車s1=Locate(G,a);s2=Locate(G,b);G.arcs[s1][s2]=G.arcs[s2][s1]=w;}}//圖G中頂點(diǎn)k的第一個鄰接頂點(diǎn)intFirstVex(GraphG,intk){if(k>=0&&k<G.vexnum){//k合理for(inti=0;i<G.vexnum;i++)if(G.arcs[k][i]!=INFINITY)returni;}return-1;}//圖G中頂點(diǎn)i的第j個鄰接頂點(diǎn)的下一個鄰接頂點(diǎn)intNextVex(GraphG,inti,intj){if(i>=0&&i<G.vexnum&&j>=0&&j<G.vexnum){//i,j合理for(intk=j+1;k<G.vexnum;k++)if(G.arcs[i][k]!=INFINITY)returnk;}return-1;}//深度優(yōu)先遍歷voidDFS(GraphG,intk){inti;if(k==-1){//第一次執(zhí)行DFS時,k為-1for(i=0;i<G.vexnum;i++)if(!visited[i])DFS(G,i);//對尚未訪問的頂點(diǎn)調(diào)用DFS}else{visited[k]=true;cout<<G.vexs[k];//訪問第k個頂點(diǎn)for(i=FirstVex(G,k);i>=0;i=NextVex(G,k,i))if(!visited[i])DFS(G,i);//對k的尚未訪問的鄰接