圖遍歷的演示

《數(shù)據(jù)結(jié)構(gòu)》課程實(shí)驗(yàn)報(bào)告 題目：圖遍歷的演示 班級(jí)： 姓名： 學(xué)號(hào)： 專業(yè)： 學(xué)院： 完成日期：需求分析問題描述：很多涉及圖上操作的算法都是以圖的遍歷操作作為基礎(chǔ)的。試寫一個(gè)程序，演示在連通圖的無向圖上訪問全部結(jié)點(diǎn)的操作?；疽螅阂脏徑佣嘀乇恚ㄟx作內(nèi)容鄰接表）為存儲(chǔ)結(jié)構(gòu)，實(shí)現(xiàn)連通無向圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷。以用戶指定的結(jié)點(diǎn)為起點(diǎn)，分別輸出每種遍歷下的結(jié)點(diǎn)訪問序列和相應(yīng)生成樹的邊集輸入的形式和輸入的范圍：先輸入頂點(diǎn)數(shù)N以及邊數(shù)M，然后依次輸入N個(gè)頂點(diǎn)，再按提示輸入M條邊的信息用（a-b3）類似的形式測(cè)試數(shù)據(jù)：教科書圖7.33部分信息概要設(shè)計(jì)抽象數(shù)據(jù)類型圖的定義：ADTGraph{數(shù)據(jù)對(duì)象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：locatevex(G,mes)；初始條件：圖G存在，mes和G中頂點(diǎn)有相同的特征。操作結(jié)果：若G中存在頂點(diǎn)u，則返回該頂點(diǎn)在圖中位置；否則返回其他信息。createudn(&G)；初始條件：圖G存在。操作結(jié)果：創(chuàng)建無向圖。createdn(&G)；初始條件：圖G存在。操作結(jié)果：創(chuàng)建有向圖。createudg(&G)；初始條件：圖G存在操作結(jié)果：創(chuàng)建無向網(wǎng)。createdg(&G)；初始條件：圖G存在。操作結(jié)果：創(chuàng)建有向網(wǎng)。DFS(G,v)；初始條件：圖G已經(jīng)存在并被賦值，v是圖中某個(gè)頂點(diǎn)的位置坐標(biāo)。操作結(jié)果：深度優(yōu)先搜索遍歷圖G，訪問頂點(diǎn)時(shí)使用函數(shù)visit.BFS(G,v)；初始條件：圖G已經(jīng)存在并被賦值，v是圖中某個(gè)頂點(diǎn)的位置坐標(biāo)。操作結(jié)果：廣度優(yōu)先搜索遍歷圖G，訪問頂點(diǎn)時(shí)使用函數(shù) rear=(rear+1)%QUEUE_SIZE;//rear后移} voidDeQueue(int&e){//若隊(duì)列不空，則刪除對(duì)頭元素，用e返回 e=base[front]; front=(front+1)%QUEUE_SIZE;} public:int*base;intfront;intrear;};查找定位函數(shù)intLocate(GraphG,charc){//圖G中查找元素c的位置 for(inti=1;i<=G.vexnum;i++){if(G.vexs[i]==c) returni; } return-1;}初始化無向圖函數(shù)voidCreateUDN(Graph&G){//創(chuàng)建無向圖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<<"輸入"<<G.vexnum<<"個(gè)頂點(diǎn)分別為:"<<endl;for(i=1;i<=G.vexnum;i++){//初始化頂點(diǎn)cout<<"頂點(diǎn):"<<i; cin>>&G.vexs[i]; temp=getchar(); }for(i=1;i<=G.vexnum;i++)//初始化鄰接矩陣for(j=1;j<=G.vexnum;j++)G.arcs[i][j]=INFINITY;//16int類型，初始化邊為無窮大cout<<"輸入"<<G.arcnum<<"條邊分別為:"<<endl;//讀取邊信息并初始化集合for(i=1;i<=G.arcnum;i++){//初始化邊cout<<"邊"<<i<<endl;scanf("%c-%c%d",&a,&b,&w);//輸入邊和權(quán)值temp=getchar();//接收回車s1=Locate(G,a); s2=Locate(G,b);G.arcs[s1][s2]=G.arcs[s2][s1]=w;}//無向}intFirstVex(GraphG,intk){//圖G中頂點(diǎn)k的第一個(gè)鄰接頂點(diǎn) if(k>=1&&k<=G.vexnum){for(inti=1;i<=G.vexnum;i++)if(G.arcs[k][i]!=INFINITY) returni; }return-1;}intNextVex(GraphG,inti,intj){//圖G中頂點(diǎn)i的第j個(gè)鄰接頂點(diǎn)的下一個(gè)鄰接頂點(diǎn) if(i>=1&&i<=G.vexnum&&j>=1&&j<=G.vexnum){//i,j合理for(intk=j+1;k<=G.vexnum;k++)if(G.arcs[i][k]!=INFINITY) returnk; }return-1;}深度優(yōu)先遍歷及廣度優(yōu)先遍歷函數(shù)voidDFS(GraphG,intk){//深度優(yōu)先搜索inti; if(k==-1){//第一次執(zhí)行DFS時(shí),k為-1for(i=1;i<=G.vexnum;i++) if(!visited[i]) DFS(G,i); }//對(duì)尚未訪問的頂點(diǎn)調(diào)用DFSelse{visited[k]=true;//訪問第k個(gè)頂點(diǎn)cout<<G.vexs[k];for(i=FirstVex(G,k);i>=1;i=NextVex(G,k,i))if(!visited[i]) DFS(G,i); }}voidBFS(GraphG){//廣度優(yōu)先搜索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); } } } }主函數(shù)voidmain(){//主函數(shù)inti; GraphG; CreateUDN(G);//創(chuàng)建無向圖visited=(bool*)malloc(G.vexnum*sizeof(bool));cout<<endl<<"深度優(yōu)先搜索結(jié)果為:";for(i=1;i<=G.vexnum;i++){ visited[i]=false;//標(biāo)志數(shù)組初始化為false DFS(G,-1);}cout<<endl<<"廣度優(yōu)先