實(shí)驗(yàn)五圖的遍歷及其應(yīng)用實(shí)現(xiàn)一、實(shí)驗(yàn)?zāi)康?．熟悉圖常用的存儲結(jié)構(gòu)。2．掌握在圖的鄰接矩陣和鄰接表兩種結(jié)構(gòu)上實(shí)現(xiàn)圖的兩種遍歷方法實(shí)現(xiàn)。3．會用圖的遍歷解決簡單的實(shí)際問題。二、需求分析很多問題都是建立在圖的遍歷的根底上實(shí)現(xiàn)的，所以必須有一個(gè)程序能夠?qū)崿F(xiàn)將圖進(jìn)行廣度和深度遍歷，必須對圖的所有節(jié)點(diǎn)進(jìn)行訪問。以無向圖為例，以無向圖的鄰接表和鄰接矩陣為存儲結(jié)構(gòu)，分別實(shí)現(xiàn)對圖進(jìn)行廣度和深度遍歷。以用戶指定的結(jié)點(diǎn)為起點(diǎn)，分別輸出每種遍歷下的結(jié)點(diǎn)訪問序列和相應(yīng)的生成樹的邊集。三、實(shí)驗(yàn)內(nèi)容[題目一]：從鍵盤上輸入圖的頂點(diǎn)和邊的信息,建立圖的鄰接表存儲結(jié)構(gòu),然后以深度優(yōu)先搜索和廣度優(yōu)先搜索遍歷該圖,并輸出起對應(yīng)的遍歷序列.試設(shè)計(jì)程序?qū)崿F(xiàn)上述圖的類型定義和根本操作,完成上述功能。該程序包括圖類型以及每一種操作的具體的函數(shù)定義和主函數(shù)。112534提示：輸入例如上圖的頂點(diǎn)和邊的信息輸入數(shù)據(jù)為：

57DGABCDE

ABAEBCCDDADBEC四、結(jié)構(gòu)算法模塊：typedefstructArcNode//定義鄰接表結(jié)構(gòu){ intadjvex;//該弧所指向的頂點(diǎn)的位置structArcNode*nextarc;//指向下一條弧的指針}ArcNode;typedefstructVNode//定義頂點(diǎn)結(jié)構(gòu)類型{ chardata;//存放頂點(diǎn)信息ArcNode*firstarc;//指向第一條依附于該定點(diǎn)的指針}VNode,Adjlist[MAX_VEX_NUM];typedefstructALGraph{ Adjlistvertices; intvexnum; intarcnum;}ALGraph;五、相關(guān)函數(shù)設(shè)計(jì)Create_DG(ALGraph&G)//創(chuàng)立一個(gè)有向圖圖的鄰接鏈表表示DFSTraverse(ALGraphG,intvex)//對圖G做深度優(yōu)先遍歷BFSTraverse(ALGraphG)//有向圖的廣度遍歷，從第v個(gè)頂點(diǎn)出發(fā)，v為頂點(diǎn)下標(biāo)locatevex(ALGraphG,charv)//圖的根本操作，尋找頂點(diǎn)位置的下標(biāo)DFS(ALGraphG,intv)//從第v個(gè)頂點(diǎn)出發(fā)遞歸地深度優(yōu)先遍歷圖G創(chuàng)立圖：請輸入圖的頂點(diǎn)數(shù)和弧數(shù)圖的創(chuàng)立輸入圖深度優(yōu)先遍歷的起點(diǎn)輸入圖的頂點(diǎn)信息深度優(yōu)先遍歷圖廣度優(yōu)先遍歷圖結(jié)束六、程序流程圖創(chuàng)立圖：請輸入圖的頂點(diǎn)數(shù)和弧數(shù)圖的創(chuàng)立輸入圖深度優(yōu)先遍歷的起點(diǎn)輸入圖的頂點(diǎn)信息深度優(yōu)先遍歷圖廣度優(yōu)先遍歷圖結(jié)束七、運(yùn)行結(jié)果截圖最初程序運(yùn)行界面如下：輸入圖的先相關(guān)信息后運(yùn)行結(jié)果(其中深度優(yōu)先遍歷的起點(diǎn)選擇的是字符所在序列的序號，且0是起點(diǎn))，一下是深度優(yōu)先遍歷時(shí)選擇不同的起點(diǎn)所出現(xiàn)的最終運(yùn)行結(jié)果：程序源代碼：//圖的鄰接表表示：#include<iostream>#include<malloc.h>#include<queue>usingnamespacestd;#defineMAX_VEX_NUM20//宏定義數(shù)組最大intvisited[MAX_VEX_NUM];//設(shè)置標(biāo)志數(shù)組queue<int>q;typedefstructArcNode//定義鄰接表結(jié)構(gòu){ intadjvex;//該弧所指向的頂點(diǎn)的位置structArcNode*nextarc;//指向下一條弧的指針}ArcNode;typedefstructVNode//定義頂點(diǎn)結(jié)構(gòu)類型{ chardata;//存放頂點(diǎn)信息ArcNode*firstarc;//指向第一條依附于該定點(diǎn)的指針}VNode,Adjlist[MAX_VEX_NUM];typedefstructALGraph{ Adjlistvertices; intvexnum; intarcnum;}ALGraph;ALGraphG;//申明一個(gè)無向圖的鄰接矩陣類型intlocatevex(ALGraphG,charv)//圖的根本操作，尋找頂點(diǎn)位置的下標(biāo){ inti=0; while(i<G.vexnum&&v!=G.vertices[i].data) i++; if(i<G.vexnum) returni;}voidCreate_DG(ALGraph&G)//創(chuàng)立一個(gè)有向圖圖的鄰接鏈表表示{ cout<<"請輸入圖的頂點(diǎn)數(shù)和弧數(shù):"<<endl; cin>>G.vexnum; cin>>G.arcnum; charv1; charv2; intv1locate; intv2locate; ArcNode*p; cout<<"輸入圖的頂點(diǎn)信息"<<endl; for(inti=0;i<G.vexnum;i++)//構(gòu)造表頭向量 { cin>>G.vertices[i].data;//輸入頂點(diǎn)值 G.vertices[i].firstarc=NULL;//初始化指針 } cout<<"請輸入從起點(diǎn)到終點(diǎn)的一條弧所對應(yīng)的頂點(diǎn)"<<endl; for(intk=1;k<=G.arcnum;k++)//輸入各弧并創(chuàng)立十字鏈表 { cin>>v1>>v2;//輸入一條弧的起點(diǎn)和終點(diǎn)v1locate=locatevex(G,v1);//確定v1在圖G中位置v2locate=locatevex(G,v2);//確定v2在圖G中位置 p=newArcNode;//假定有足夠空間 p->adjvex=v2locate;//有一條弧指向v2 p->nextarc=G.vertices[v1locate].firstarc;//對弧節(jié)點(diǎn)賦值 G.vertices[v1locate].firstarc=p;//完成在入弧和出弧鏈表的插入/*q=newArcNode; q->adjvex=v1locate; q->nextarc=G.vertices[v2locate].firstarc; G.vertices[v2locate].firstarc=q;*/ }}//Create_DGvoidDFS(ALGraphG,intv)//從第v個(gè)頂點(diǎn)出發(fā)遞歸地深度優(yōu)先遍歷圖G{visited[v]=1;//訪問第v個(gè)節(jié)點(diǎn) cout<<G.vertices[v].data<<"";//輸出節(jié)點(diǎn)值 for(ArcNode*p=G.vertices[v].firstarc;p;p=p->nextarc) { if(!visited[p->adjvex])DFS(G,p->adjvex);//對v的尚未訪問的鄰接頂點(diǎn)p遞歸調(diào)用dfs }}//DFSvoidDFSTraverse(ALGraphG,intvex)//對圖G做深度優(yōu)先遍歷{ for(inti=0;i<G.vexnum;i++) visited[i]=0; //訪問數(shù)組初始化 DFS(G,vex); //先對圖從指定定點(diǎn)訪問 for(intv=0;v<G.vexnum;v++) //對可能出現(xiàn)的子圖遍歷 if(!visited[v])//對尚未訪問的頂點(diǎn)調(diào)用dfs DFS(G,v);}//DFSTraverseintBFSTraverse(ALGraphG)//無向圖的廣度遍歷，從第v個(gè)頂點(diǎn)出發(fā)，v為頂點(diǎn)下標(biāo){for(inti=0;i<G.vexnum;i++) //訪問數(shù)組初始化 visited[i]=0; q.empty();intv; intu; for(v=0;v<G.vexnum;v++) if(!visited[v])//v尚未被訪問 { visited[v]=1; cout<<G.vertices[v].data<<""; q.push(v);//V入隊(duì)列 while(!q.empty()) { u=q.front();//對頭元素出隊(duì)并置為u q.pop(); for(ArcNode*p=G.vertices[v].firstarc;p;p=p->nextarc) if(!visited[p->adjvex])//p為u的尚未訪問的鄰接節(jié)點(diǎn) { visited[p->adjvex]=1; cout<<G.vertices[p->adjvex].data<<""; q.push(p->adjvex); }//if }//while }//if return1;}//