C++圖的創(chuàng)建與遍歷實驗報告

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

57DGABCDE

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