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

一、需求分析以鄰接表為存儲(chǔ)結(jié)構(gòu)，實(shí)現(xiàn)連通無向圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷。以用戶指定的節(jié)點(diǎn)為起點(diǎn)，分別輸出每種遍歷下的節(jié)點(diǎn)訪問序列和相應(yīng)的生成樹的邊集。二、概要設(shè)計(jì)1、圖的鄰接表存儲(chǔ)表示1、邊的結(jié)構(gòu)定義typedefstructArcNode{鄰接點(diǎn)的下標(biāo)adjvex; 后繼鏈指針*nextarc}ArcNode;2、頂點(diǎn)的結(jié)構(gòu)類型定義typedefstructVNode{ 頂點(diǎn)信息data 指向第一條依附該頂點(diǎn)的弧的指針firstarc}VNode,存放點(diǎn)的鄰接表AdjList[Maxnum];3、圖的定義typedefstruct{ 鄰接表vertices; 圖的當(dāng)前頂點(diǎn)數(shù)vexnum和弧數(shù)arcnum; 圖的種類kind0-表示無向圖，2-表示有向圖}Graph;2、隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)1.鏈表節(jié)點(diǎn)類型定義typedefstructQNode{ 數(shù)據(jù)data; 下一個(gè)隊(duì)員指針*next;}QNode,/指針數(shù)組Qnode2、鏈表定義typedefstruct{ 隊(duì)頭front; 隊(duì)尾rear;}Queue;3、圖的函數(shù)1、獲取頂點(diǎn)的下標(biāo)〔//返回頂點(diǎn)v在圖中的位置函數(shù)〕intLocateVex(Graph&G,intv){ 遍歷頂點(diǎn)順序表得到頂點(diǎn)下標(biāo)并返回；不到那么返回-1；}2、數(shù)組用于表示標(biāo)志是否被訪問boolVisited[Maxnum];4、隊(duì)列函數(shù)1、構(gòu)造一個(gè)空隊(duì)列QintInitQueue(Queue&Q){構(gòu)造一個(gè)空隊(duì)列Q隊(duì)頭和隊(duì)尾同指向一個(gè)地址；隊(duì)頭和隊(duì)尾的next指向null; }2、插入隊(duì)尾元素intEnQueue(Queue&Q,inte){插入元素e為Q的新的隊(duì)尾元素;隊(duì)尾元素的下一個(gè)元素為空；}3、隊(duì)頭出隊(duì)intDeQueue(Queue&Q,int&e){隊(duì)列不為空，那么刪除Q的對(duì)頭元素，用e返回其值； 釋放隊(duì)頭元素的；}4、判斷隊(duì)列是否為空intQueueEmpty(QueueQ){隊(duì)列為空返回1否那么返回0；}5、構(gòu)造鄰接表結(jié)構(gòu)的圖GvoidCreateGraph(Graph&G){用戶輸入選擇圖的類型；用戶輸入圖的邊數(shù)、頂點(diǎn)數(shù)；初始化頂點(diǎn)的信息和指向第一個(gè)頂點(diǎn)為空；用戶輸入邊的信息；形成鄰接鏈表的存儲(chǔ)方式； 打印鄰接鏈表；}6、深度優(yōu)先遍歷圖-voidDFS(GraphG,intv){ 通過遞歸實(shí)現(xiàn)深度優(yōu)先遍歷}7、廣度優(yōu)先遍歷圖voidBFS(GraphG,intv){用隊(duì)列來輔助實(shí)現(xiàn)廣度的優(yōu)先遍歷；}8、深度優(yōu)先遍歷生成樹voidDFSTraverse(Graph&G,intv){ 通過深度的優(yōu)先遍歷輸出生成樹的邊集；}9、廣度優(yōu)先遍歷生成樹voidBFSTraverse(Graph&G,intv){ 用廣度優(yōu)先遍歷輸出廣度優(yōu)先遍歷的生成樹邊集；}10、主函數(shù)intmain(){ 創(chuàng)立圖； CreateGraph(G); 請(qǐng)輸入訪問的頭頂點(diǎn)； 深度優(yōu)先遍歷圖； DFS(G,u); 打印深度優(yōu)先遍歷圖的生成樹的邊集； DFSTraverse(G,u); 廣度優(yōu)先遍歷圖 BFS(G,u); 打印廣度優(yōu)先遍歷圖的生成樹的邊集 BFSTraverse(G,u);}三、詳細(xì)設(shè)計(jì)1、圖的鄰接表存儲(chǔ)表示#defineMaxnum30//最大頂點(diǎn)數(shù)typedefstructArcNode{ intadjvex;//鄰接點(diǎn)的下標(biāo) structArcNode*nextarc;//后繼鏈指針}ArcNode;typedefstructVNode{ intdata;//頂點(diǎn)信息 ArcNode*firstarc;//指向第一條依附該頂點(diǎn)的弧的指針}VNode,AdjList[Maxnum];typedefstruct{ AdjListvertices;//鄰接表 intvexnum,arcnum;//圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù) intkind;//圖的種類0-表示無向圖，2-表示有向圖}Graph;2、隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)typedefstructQNode{ intdata; structQNode*next;}QNode,*Qnode;//指針數(shù)組Qnodetypedefstruct{ Qnodefront; Qnoderear;}Queue;3、圖的函數(shù)intLocateVex(Graph&G,intv){//返回頂點(diǎn)v在圖中的位置函數(shù) inti; for(i=0;i<G.vexnum;++i) if(G.vertices[i].data==v) break; else continue; if(i<G.vexnum) returni; else return-1;}boolVisited[Maxnum];4、隊(duì)列函數(shù)//構(gòu)造一個(gè)空隊(duì)列QintInitQueue(Queue&Q){ Q.front=Q.rear=newQNode; if(!Q.front) return1; Q.front->next=NULL; return0;}//插入元素e為Q的新的隊(duì)尾元素intEnQueue(Queue&Q,inte){ Qnodep=newQNode; if(!p) return1; p->data=e; p->next=NULL; Q.rear->next=p; Q.rear=p; return0;}//隊(duì)列不為空，那么刪除Q的對(duì)頭元素，用e返回其值intDeQueue(Queue&Q,int&e){ Qnodep; //if(Q.front==Q.rear) //return-1; p=Q.front->next; Q.front->next=p->next; if(Q.rear==p) Q.rear=Q.front; e=p->data; free(p); return1;}//判斷是否隊(duì)空intQueueEmpty(QueueQ){ if(Q.rear==Q.front) return1; else return0;}5、構(gòu)造鄰接表結(jié)構(gòu)的圖GvoidCreateGraph(Graph&G){ inti,j,k,v1,v2; ArcNode*p,*q; intv,m,kin; cout<<"請(qǐng)輸入圖的種類，0-表示無向圖，2-表示有向圖："; cin>>kin; cout<<"請(qǐng)輸入頂點(diǎn)的個(gè)數(shù)："; cin>>v; cout<<"請(qǐng)輸入邊的條數(shù)："; cin>>m; G.vexnum=v; G.arcnum=m; G.kind=kin; for(k=0;k<G.vexnum;k++){ G.vertices[k].data=k+1;//每個(gè)頂點(diǎn)信息 G.vertices[k].firstarc=NULL;//初始化 } cout<<"請(qǐng)輸入邊,邊的頂點(diǎn)用一個(gè)編號(hào)表示，全部n個(gè)頂點(diǎn)用1-n表示：\n"; for(k=0;k<G.arcnum;k++){ cout<<"請(qǐng)輸入第"<<k+1<<"條邊"; cin>>v1>>v2; i=LocateVex(G,v1); j=LocateVex(G,v2); p=newArcNode; p->adjvex=j; p->nextarc=G.vertices[i].firstarc;//頭插法插入 G.vertices[i].firstarc=p; if(G.kind==0){//無向圖 p=newArcNode; p->adjvex=i; p->nextarc=G.vertices[j].firstarc; G.vertices[j].firstarc=p; } } cout<<"輸入的圖的鄰接表如下：\n";//輸出鄰接表 for(k=0;k<G.vexnum;k++){ cout<<k<<""<<"v"<<G.vertices[k].data; q=G.vertices[k].firstarc; while(q->nextarc){ cout<<"->"<<(q->adjvex)+1; q=q->nextarc; } cout<<"->"<<(q->adjvex)+1<<"\n"; }}6、深度優(yōu)先遍歷圖-voidDFS(GraphG,intv){ ArcNode*p; if(G.vertices[v].data==NULL)//注意輸入v后，v要減1 cout<<"ERROR"; else{ if(Visited[v]==0){ //訪問 cout<<"v"<<G.vertices[v].data<<"->"; Visited[v]=1; for(p=G.vertices[v].firstarc;p!=NULL;p=p->nextarc) //未被訪問 if(Visited[p->adjvex]==0) DFS(G,p->adjvex); } }}7、廣度優(yōu)先遍歷圖voidBFS(GraphG,intv){ inti; intw=0; ArcNode*p; QueueQ; //定義一個(gè)隊(duì)列 if(G.vertices[v].data==NULL) cout<<"ERROR"; else{ for(i=0;i<G.vexnum;i++) Visited[i]=0;//初始化頂點(diǎn)，均未被訪問過 InitQueue(Q);//初始化隊(duì)列，構(gòu)造一個(gè)空的隊(duì)列 if(Visited[v]==0){ cout<<"v"<<G.vertices[v].data<<"->"; Visited[v]=1; EnQueue(Q,v);//第一個(gè)頂點(diǎn)入隊(duì) while(!QueueEmpty(Q)){ DeQueue(Q,w);//第一個(gè)頂點(diǎn)出隊(duì) for(p=G.vertices[w].firstarc;p!=NULL;p=p->nextarc){ if(Visited[p->adjvex]==0){ cout<<"v"<<G.vertices[p->adjvex].data<<"->"; Visited[p->adjvex]=1; EnQueue(Q,p->adjvex); }//if }//for }//while }//if }}8、深度優(yōu)先遍歷生成樹voidDFSTraverse(Graph&G,intv){ ArcNode*p; // if(Visited[v]==0){ Visited[v]=1; for(p=G.vertices[v].firstarc;p!=NULL;p=p->nextarc) if(Visited[p->adjvex]==0){ cout<<"<"<<"v"<<G.vertices[v].data; cout<<","<<"v"<<G.vertices[p->adjvex].data<<">"<<","; DFSTraverse(G,p->adjvex); } }}9、廣度優(yōu)先遍歷生成樹voidBFSTraverse(Graph&G,intv){ inti; intw=0; ArcNode*p; QueueQ; //定義一個(gè)隊(duì)列 if(G.vertices[v].data==NULL) cout<<"ERROR"; else{ for(i=0;i<G.vexnum;i++) Visited[i]=0;//初始化頂點(diǎn)，均未被訪問過 InitQueue(Q);//初始化隊(duì)列，構(gòu)造一個(gè)空的隊(duì)列 if(Visited[v]==0){ Visited[v]=1; EnQueue(Q,v);//第一個(gè)頂點(diǎn)入隊(duì) while(!QueueEmpty(Q)){ DeQueue(Q,w);//第一個(gè)頂點(diǎn)出隊(duì) for(p=G.vertices[w].firstarc;p!=NULL;p=p->nextarc){ if(Visited[p->adjvex]==0){ cout<<"<"<<"v"<<G.vertices[w].data; cout<<","<<"v"<<G.vertices[p->adjvex].data<<">"<<","; Visited[p->adjvex]=1; EnQueue(Q,p->adjvex); }//if }//for }//while }//if }}10、主函數(shù)intmain(){ intu; GraphG; CreateGraph(G); cout<<"請(qǐng)輸入訪問的頭頂點(diǎn)："; cin>>u; u=u-1; cout<<"深度優(yōu)先遍歷圖的序列如下："<<endl;; DFS(G,u); cout<<endl; cout<<"深度優(yōu)先遍歷圖的生成樹的邊集："<<endl<<"{"; for(inti=0;i<G.vexnum;i++) Visited[i]=0;//對(duì)圖初始化，均未被訪問過 DFSTraverse(G,u); cout<<"}"<<endl; cout<<"廣度優(yōu)先遍歷圖的序列如下："<<endl; BFS(G,u); cout<<endl; cout<<"廣度優(yōu)先遍歷圖的生成樹的邊集："<<endl<<"{"; for(intj=0;j<G.vexnum;j++) Visited[i]=0;//對(duì)圖初始化，均未被訪問過 BFSTraverse(G,u); cout<<"}"<<endl; return0;}四、調(diào)試分析原本是用多重鏈表的存儲(chǔ)方式存儲(chǔ)圖，后來發(fā)現(xiàn)算法太復(fù)雜換而改用鄰接鏈表存儲(chǔ)；五、用戶使用說明本程序的運(yùn)行環(huán)境為MicrosoftVisualC++6.0。按提示鍵盤輸入圖的信息；接受其他命令后即執(zhí)行相應(yīng)運(yùn)算和顯示相應(yīng)結(jié)果。關(guān)閉窗口那么退出程序。六、測試結(jié)果

七、源代碼///////////////////////////////////////////////////////////用鄰接表的存儲(chǔ)方式存儲(chǔ)圖實(shí)現(xiàn)圖的廣度和深度的優(yōu)先遍歷//并輸出每種遍歷下的節(jié)點(diǎn)訪問序列和相應(yīng)生成樹的邊集///////////////////////////////////////////////////////#include<iostream>usingnamespacestd;//--------圖的鄰接表存儲(chǔ)表示---------#defineMaxnum30//最大頂點(diǎn)數(shù)typedefstructArcNode{ intadjvex;//鄰接點(diǎn)的下標(biāo) structArcNode*nextarc;//后繼鏈指針}ArcNode;typedefstructVNode{ intdata;//頂點(diǎn)信息 ArcNode*firstarc;//指向第一條依附該頂點(diǎn)的弧的指針}VNode,AdjList[Maxnum];typedefstruct{ AdjListvertices;//鄰接表 intvexnum,arcnum;//圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù) intkind;//圖的種類0-表示無向圖，2-表示有向圖}Graph;//--------------隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)-----------------typedefstructQNode{ intdata; structQNode*next;}QNode,*Qnode;//指針數(shù)組Qnodetypedefstruct{ Qnodefront; Qnoderear;}Queue;//***********圖的函數(shù)******************intLocateVex(Graph&G,intv){//返回頂點(diǎn)v在圖中的位置函數(shù) inti; for(i=0;i<G.vexnum;++i) if(G.vertices[i].data==v) break; else continue; if(i<G.vexnum) returni; else return-1;}boolVisited[Maxnum];//*************隊(duì)列函數(shù)***********************intInitQueue(Queue&Q){//構(gòu)造一個(gè)空隊(duì)列Q Q.front=Q.rear=newQNode; if(!Q.front) return1; Q.front->next=NULL; return0;}intEnQueue(Queue&Q,inte){//插入元素e為Q的新的隊(duì)尾元素 Qnodep=newQNode; if(!p) return1; p->data=e; p->next=NULL; Q.rear->next=p; Q.rear=p; return0;}intDeQueue(Queue&Q,int&e){//隊(duì)列不為空，那么刪除Q的對(duì)頭元素，用e返回其值 Qnodep; //if(Q.front==Q.rear) //return-1; p=Q.front->next; Q.front->next=p->next; if(Q.rear==p) Q.rear=Q.front; e=p->data; free(p); return1;}intQueueEmpty(QueueQ){//判斷是否隊(duì)空 if(Q.rear==Q.front) return1; else return0;}//-----構(gòu)造鄰接表結(jié)構(gòu)的圖G------------voidCreateGraph(Graph&G){ inti,j,k,v1,v2; ArcNode*p,*q; intv,m,kin; cout<<"請(qǐng)輸入圖的種類，0-表示無向圖，2-表示有向圖："; cin>>kin; cout<<"請(qǐng)輸入頂點(diǎn)的個(gè)數(shù)："; cin>>v; cout<<"請(qǐng)輸入邊的條數(shù)："; cin>>m; G.vexnum=v; G.arcnum=m; G.kind=kin; for(k=0;k<G.vexnum;k++){ G.vertices[k].data=k+1;//每個(gè)頂點(diǎn)信息 G.vertices[k].firstarc=NULL;//初始化 } cout<<"請(qǐng)輸入邊,邊的頂點(diǎn)用一個(gè)編號(hào)表示，全部n個(gè)頂點(diǎn)用1-n表示：\n"; for(k=0;k<G.arcnum;k++){ cout<<"請(qǐng)輸入第"<<k+1<<"條邊"; cin>>v1>>v2; i=LocateVex(G,v1); j=LocateVex(G,v2); p=newArcNode; p->adjvex=j; p->nextarc=G.vertices[i].firstarc;//頭插法插入 G.vertices[i].firstarc=p; if(G.kind==0){//無向圖 p=newArcNode; p->adjvex=i; p->nextarc=G.vertices[j].firstarc; G.vertices[j].firstarc=p; } } cout<<"輸入的圖的鄰接表如下：\n";//輸出鄰接表 for(k=0;k<G.vexnum;k++){ cout<<k<<""<<"v"<<G.vertices[k].data; q=G.vertices[k].firstarc; while(q->nextarc){ cout<<"->"<<(q->adjvex)+1; q=q->nextarc; } cout<<"->"<<(q->adjvex)+1<<"\n"; }}//------------深度優(yōu)先遍歷圖-------------------voidDFS(GraphG,intv){ ArcNode*p; if(G.vertices[v].data==NULL)//注意輸入v后，v要減1 cout<<"ERROR"; else{ if(Visited[v]==0){ //訪問 cout<<"v"<<G.vertices[v].data<<"->"; Visited[v]=1; for(p=G.vertices[v].firstarc;p!=NULL;p=p->nextarc) //未被訪問 if(Visited[p->adjvex]==0) DFS(G,p->adjvex); } }}//--------------廣度優(yōu)先遍歷圖-----------------voidBFS(GraphG,intv){ inti; intw=0; ArcNode*p; QueueQ; //定義一個(gè)隊(duì)列 if(G.vertices[v].data==NULL) cout<<"ERROR"; else{ for(i=0;i<G.vexnum;i++) Visited[i]=0;//初始化頂點(diǎn)，均未被訪問過 InitQueue(Q);//初始化隊(duì)列，構(gòu)造一個(gè)空的隊(duì)列 if(Visited[v]==0){ cout<<"v"<<G.vertices[v].data<<"->"; Visited[v]=1; EnQueue(Q,v);//第一個(gè)頂點(diǎn)入隊(duì) while(!QueueEmpty(Q)){ DeQueue(Q,w);//第一個(gè)頂點(diǎn)出隊(duì) for(p=G.vertices[w].firstarc;p!=NULL;p=p->nextarc){ if(Visited[p->adjvex]==0){ cout<<"v"<<G.vertices[p->adjvex].data<<"->"; Visited[p->adjvex]=1; EnQueue(Q,p->adjvex); }//if }//for }//while }//if }}//*************深度優(yōu)先遍歷生成樹********************voidDFSTraverse(Graph&G,intv){ ArcNode*p; if(Visited[v]==0){ Visited[v]=1; for(p=G.vertices[v].firstarc;p!=NULL;p=p->nextarc) if(Visited[p->adjvex]==0){ cout<<"<"<<"v"<<G.vertices[v].data; cout<<","<<"v"<<G.vertices[p->adjvex].data<<">"<<","; DFSTraverse(G,p->adjvex); } }}//*************廣度優(yōu)先遍歷生成樹**************