數據結構圖的遍歷實驗報告

..題目：圖的遍歷的實現需求分析本演示程序中,輸入的數據類型均為整型數據,不允許輸入字符等其他數據類型,且需要按照提示內容進行輸入,成對的關系數據必須在所建立的圖中已經存在對應的結點。演示程序以用戶和計算機的對話方式執行,在計算機終端上顯示的提示信息的說明下,按照要求輸入數據,運算結果在其后顯示。本程序實現分別基于鄰接矩陣和鄰接表存儲結構的有、無向圖,有、無向網的建立和遍歷。遍歷分DFS和BFS兩種算法,并分別以遞歸和非遞歸形式實現。測試數據：無向圖結點數4弧數3結點：1234結點關系：12；13；24有向圖結點數6弧數6結點：123456結點關系：12；13；24；35；36；25概要設計為實現上述程序功能,圖的存儲結構分為鄰接矩陣和鄰接表兩種。遍歷過程中借助了棧和隊列的存儲結構。鄰接矩陣存儲結構的圖定義：ADTmgraph{數據對象V：V是具有相同特性的的數據元素的集合,成為頂點集。數據關系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中頂點有相同的特征。操作結果：若G中存在頂點u,則返回該頂點在圖中位置；否則返回其他信息。createudn<&G>；初始條件：圖G存在。操作結果：創建無向圖。createdn<&G>；初始條件：圖G存在。操作結果：創建有向圖。createudg<&G>；初始條件：圖G存在。操作結果：創建無向網。createdg<&G>；初始條件：圖G存在。操作結果：創建有向網。DFS<G,v>；初始條件：圖G已經存在并被賦值,v是圖中某個頂點的位置坐標。操作結果：深度優先搜索遍歷圖G,訪問頂點時使用函數visit.BFS<G,v>；初始條件：圖G已經存在并被賦值,v是圖中某個頂點的位置坐標。操作結果：廣度優先搜索遍歷圖G,訪問頂點時使用函數visit.visit<a>；初始條件：a為圖中的某個頂點值。操作結果：訪問頂點a,本程序中作用結果為輸出頂點值。｝ADTmgraph鄰接表存儲結構的圖定義：ADTalgraph{數據對象V：V是具有相同特性的的數據元素的集合,成為頂點集。數據關系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中頂點有相同的特征。操作結果：若G中存在頂點u,則返回該頂點在圖中位置；否則返回其他信息。createudn<&G>；初始條件：圖G存在。操作結果：創建無向圖。createdn<&G>；初始條件：圖G存在。操作結果：創建有向圖。createudg<&G>；初始條件：圖G存在。操作結果：創建無向網。createdg<&G>；初始條件：圖G存在。操作結果：創建有向網。DFS<G,v>；初始條件：圖G已經存在并被賦值,v是圖中某個頂點的位置坐標。操作結果：深度優先搜索遍歷圖G,訪問頂點時使用函數visit.BFS<G,v>；初始條件：圖G已經存在并被賦值,v是圖中某個頂點的位置坐標。操作結果：廣度優先搜索遍歷圖G,訪問頂點時使用函數visit.visit<a>；初始條件：a為圖中的某個頂點值。操作結果：訪問頂點a,本程序中作用結果為輸出頂點值。｝ADTalgraph主程序流程：定義并創建圖statuscreatgraph<mgraph&G>{cout<<"請選擇構造的圖的類型：〔1:有向圖,2:有向網,3:無向圖,4:無向網"<<endl;intkind;scanf<"%d",&kind>;switch<kind>//通過選擇確定創建哪一種圖；{case1:returncreatedg<G>;case2:returncreatedn<G>;case3:returncreateudg<G>;case4:returncreateudn<G>;default:returnerror;}}然后采用DFS或BFS進行遍歷〔訪問結果為輸出頂點值。4.函數的調用關系圖：maincreatgraphDFS<BFS>createdgcreatedncreateudgcreateudn visitinitstackpushdestroystacklocatevexpopgettopvisitlocatevexlinkqueueenqueuegetheaddequeuedestroyqueue其中,當DFS使用遞歸算法時相關的棧操作不使用,當BFS使用遞歸算法時相關的隊列操作仍有部分使用。調試分析采用鄰接表結構創建圖時,由于沒有正確進行弧元素的跟進插入,導致圖創建不成功。沒有采用多文件結構,導致在快要完成時發現函數定義的位置不盡合理,后續添加功能時難度增大。本程序主要為實現遍歷算法思想,對實用性考慮偏少,但考慮到了多種數據類型情況下的分別實現,函數拆分較詳細,算法可靠性強。算法的時空分析由于對頂點元素的存儲均采用了線性結構,所以在創建圖和遍歷時多依賴于該線性存儲的大小。當結點個數為n,弧條數為e時,createdgcreatedncreateudgcreateudn的算法時間復雜度都為O<n2+e*n>,其中對鄰接矩陣的初始化耗費了O<n2的時間。當用二維數組表示鄰接矩陣作為圖的存儲結構時,查找每個頂點的鄰接點所需時間為O<n2,而以鄰接表為存儲結構時為O<e。以鄰接表為存儲結構時,深度優先搜索遍歷圖〔DFS的時間復雜度為O<n+e>。廣度優先搜索遍歷圖〔BFS的時間復雜度和深度優先搜索遍歷〔DFS相同。5.對鏈表的操作需要很重要的一個量來定位鏈表和定位操作的位置,指針的作用不可替代。多種數據結構的聯合使用在程序中非常重要,多種存儲結構的程序實現原理上相同,但具體的操作技巧有很大差別。用戶使用說明本程序運行環境建議為windowxp.打開程序工程,并運行其中可執行文件,終端對話框會出現文字提示,請嚴格按照文字提示進行輸入操作。數據之間的分隔可用空格或回車鍵執行。如下圖是某無向圖的創建并進行DFS的結果：結果隨后出現按照文字提示進行輸入數據分隔使用空格或回車結果隨后出現按照文字提示進行輸入數據分隔使用空格或回車測試結果DFS:附錄鄰接矩陣結構創建圖：#include<iostream>#include<string.h>#include<stdio.h>typedefintvertextype;typedefintinfotype;typedefintstatus;typedefintselemtype;#defineerror0#defineok1#defineINFINTYINT_MAX//最大值∞#defineMAX_VERTEX_NUM20//最大定點個數#defineFALSE0#defineTRUE1#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10#defineoverflow-2usingnamespacestd;//弧定義typedefstructarccell{intadj;//infotype*info;}arccell,adjmatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//圖定義typedefstruct{vertextypevexs[MAX_VERTEX_NUM];//頂點adjmatrixarcs;//弧矩陣intvexnum,arcnum;}mgraph;intlocatevex<mgraphG,vertextypemes>{for<inti=0;i<G.vexnum;++i>if<mes==G.vexs[i]>returni;return0;}//定位函數//創建無向網statuscreateudn<mgraph&G>{cout<<"請輸入無向網的頂點數,弧數："<<endl;//可添加info選項。。。。。。。scanf<"%d%d",&G.vexnum,&G.arcnum>;cout<<"請輸入各頂點的值："<<endl;for<inti=0;i<G.vexnum;++i>scanf<"%d",&G.vexs[i]>;//構造頂點for<inti=0;i<G.vexnum;++i>for<intj=0;j<G.vexnum;++j>G.arcs[i][j].adj=0;cout<<"請輸入成對的關系頂點數值以及其權值：〔形如：11221"<<endl;for<intk=0;k<G.arcnum;++k>{vertextypev1,v2;intw;scanf<"%d%d%d",&v1,&v2,&w>;inti=locatevex<G,v1>;intj=locatevex<G,v2>;G.arcs[i][j].adj=w;G.arcs[j][i]=G.arcs[i][j];}returnok;}//創建有向網statuscreatedn<mgraph&G>{cout<<"請輸入有向網的頂點數,弧數："<<endl;//可添加info選項。。。。。。。scanf<"%d%d",&G.vexnum,&G.arcnum>;cout<<"請輸入各頂點的值："<<endl;for<inti=0;i<G.vexnum;++i>scanf<"%d",&G.vexs[i]>;//構造頂點for<inti=0;i<G.vexnum;++i>for<intj=0;j<G.vexnum;++j>G.arcs[i][j].adj=0;cout<<"請輸入成對的關系頂點數值以及其權值：〔形如：11221"<<endl;for<intk=0;k<G.arcnum;++k>{vertextypev1,v2;intw;scanf<"%d%d%d",&v1,&v2,&w>;inti=locatevex<G,v1>;intj=locatevex<G,v2>;G.arcs[i][j].adj=w;}returnok;}//創建無向圖statuscreateudg<mgraph&G>{cout<<"請輸入無向圖的頂點數,弧數："<<endl;//可添加info選項。。。。。。。scanf<"%d%d",&G.vexnum,&G.arcnum>;cout<<"請輸入各頂點的值："<<endl;for<inti=0;i<G.vexnum;++i>scanf<"%d",&G.vexs[i]>;//構造頂點for<inti=0;i<G.vexnum;++i>for<intj=0;j<G.vexnum;++j>G.arcs[i][j].adj=0;cout<<"請輸入成對的關系頂點數值：〔形如：1122"<<endl;for<intk=0;k<G.arcnum;++k>{vertextypev1,v2;scanf<"%d%d",&v1,&v2>;inti=locatevex<G,v1>;intj=locatevex<G,v2>;G.arcs[i][j].adj=1;G.arcs[j][i]=G.arcs[i][j];}returnok;}//創建有向圖statuscreatedg<mgraph&G>{cout<<"請輸入有向圖的頂點數,弧數："<<endl;//可添加info選項。。。。。。。scanf<"%d%d",&G.vexnum,&G.arcnum>;cout<<"請輸入各頂點的值："<<endl;for<inti=0;i<G.vexnum;++i>scanf<"%d",&G.vexs[i]>;//構造頂點for<inti=0;i<G.vexnum;++i>for<intj=0;j<G.vexnum;++j>G.arcs[i][j].adj=0;cout<<"請輸入成對的關系頂點數值：〔形如：1122"<<endl;for<intk=0;k<G.arcnum;++k>{vertextypev1,v2;scanf<"%d%d",&v1,&v2>;inti=locatevex<G,v1>;intj=locatevex<G,v2>;G.arcs[i][j].adj=1;}returnok;}鄰接矩陣的DFS非遞歸算法：voidvisit<vertextypea>{printf<"--%d-",a>;}voidDFS<mgraphG,intv>{intvisitp[MAX_VERTEX_NUM];sqstackS;if<initstack<S>==1>;for<inti=0;i<G.vexnum;i++>visitp[i]=FALSE;//首先訪問第一個頂點visit<G.vexs[v]>;visitp[v]=TRUE;push<S,G.vexs[v]>;while<S.top!=S.base>//若棧不為空,則繼續從棧頂元素進行遍歷{intk=0,m=0,num=0,j=0,temp=0;gettop<S,k>;m=locatevex<G,k>;//得到棧頂元素,并在圖中定位for<j=0;j<G.vexnum;j++>if<<G.arcs[m][j].adj>!=0&&visitp[j]==FALSE>num+=1;if<num==0>//如果與棧頂元素相關聯的頂點都被訪問過,則刪除棧頂元素pop<S,temp>;//如果與棧頂元素相關聯的頂點還有未被訪問的,//則將與其相關聯的頂點全部訪問elsefor<intw=0;w<G.vexnum;w++>if<G.arcs[m][w].adj!=0&&visitp[w]==FALSE>{visit<G.vexs[w]>;//執行visit操作visitp[w]=TRUE;//訪問標志置真push<S,G.vexs[w]>;//剛訪問的頂點入棧break;}}destroystack<S>;}鄰接矩陣的DFS遞歸算法：intvisitp[MAX_VERTEX_NUM];//全局變量,//注意在main函數中都賦初值FALSEvoidvisit<vertextypea>{printf<"--%d-",a>;}voidDFS<mgraphG,intv>{visit<G.vexs[v]>;visitp[v]=TRUE;for<intj=0;j<G.vexnum;j++>if<<G.arcs[v][j].adj>!=0&&visitp[j]==FALSE>DFS<G,j>;}鄰接矩陣存儲結構的BFS非遞歸算法：voidvisit<vertextypea>{printf<"--%d-",a>;}voidBFS<mgraphG,intv>{intvisitp[MAX_VERTEX_NUM];linkqueueQ;if<initqueue<Q>==1>for<inti=0;i<G.vexnum;i++>visitp[i]=FALSE;elseexit<1>;//首先訪問第一個頂點visit<G.vexs[v]>;visitp[v]=TRUE;enqueue<Q,G.vexs[v]>;while<Q.front!=Q.rear>{intk=0,m=0,num=0,temp=0,j=0;gethead<Q,k>;m=locatevex<G,k>;//得到隊首元素并定位for<j=0;j<G.vexnum;j++>if<<G.arcs[m][j].adj>!=0&&visitp[j]==FALSE>num+=1;if<num==0>dequeue<Q,temp>;//如果此頂點的后繼均訪問過,則從隊列中刪除else{for<intw=0;w<G.vexnum;w++>if<G.arcs[m][w].adj!=0&&visitp[w]==FALSE>{visit<G.vexs[w]>;//執行visit操作visitp[w]=TRUE;//訪問標志置真enqueue<Q,G.vexs[w]>;}}}destroyqueue<Q>;}鄰接矩陣存儲結構的BFS遞歸算法：voidBFS<mgraphG,intv>{linkqueueQ;initqueue<Q>;if<visitp[v]==FALSE>{visit<G.vexs[v]>;visitp[v]=TRUE;}intj;inte;intaddress;for<j=0;j<G.vexnum;j++>if<<G.arcs[v][j].adj>!=0&&visitp[j]==FALSE>{visit<G.vexs[j]>;visitp[j]=TRUE;enqueue<Q,G.vexs[j]>;}while<Q.front!=Q.rear>{dequeue<Q,e>;address=locatevex<G,e>;BFS<G,address>;}destroyqueue<Q>;}intmain<>{mgraphG;creatgraph<G>;inti;for<i=0;i<G.vexnum;i++>visitp[i]=FALSE;BFS<G,0>;return0;}鄰接表存儲結構的圖的創建：#include<stdio.h>#include<iostream>#include<stdlib.h>typedefintvertextype;typedefintinfotype;typedefintstatus;typedefintselemtype;#defineFALSE0#defineTRUE1#defineerror0#defineok1#defineMAX_VERTEX_NUM20//最大頂點個數#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10#defineoverflow-2usingnamespacestd;typedefstructarcnode{ intadjvex;//弧指向的頂點的位置 intadj;//權值 structarcnode*nextrarc;//指向下一條弧的指針 infotype*info;}arcnode;//頂點結點定義typedefstructvnode{ vertextypedata;//頂點數據 arcnode*firsttarc;//指向第一條依附該頂點的弧的指針}vnode,adjlist[MAX_VERTEX_NUM];//圖定義typedefstruct{ adjlistvertices;//頂點數組 intvexnum,arcnum;//頂點數目,弧數目 intkind;//圖的種類標志,以數字代表}algraph;intlocatevex<algraphG,vertextypemes>{for<inti=0;i<G.vexnum;++i>if<mes==G.vertices[i].data>returni;return-1;}//創建無向網statuscreateudn<algraph&G>{cout<<"請輸入無向網的頂點數,弧數："<<endl;scanf<"%d%d",&G.vexnum,&G.arcnum>;//輸入頂點數和弧數cout<<"請輸入各頂點的值："<<endl;for<inti=0;i<G.vexnum;++i>scanf<"%d",&G.vertices[i].data>;//輸入并構造頂點for<inti=0;i<G.vexnum;++i>G.vertices[i].firsttarc=NULL;//初始化指針firsttarccout<<"請輸入成對的關系頂點數值以及其權值：〔形如：11221"<<endl;for<intk=0;k<G.arcnum;++k>//輸入相聯系的兩數據{vertextypev1,v2;intw;//權值scanf<"%d%d%d",&v1,&v2,&w>;getchar<>;inti=locatevex<G,v1>;intj=locatevex<G,v2>;//定位arcnode*a;a=<arcnode*>malloc<sizeof<arcnode>>;//為加入的弧結點申請空間if<a==NULL>exit<1>;<*a>.adjvex=j;<*a>.adj=w;<*a>.nextrarc=NULL;<*a>.info=NULL;if<G.vertices[i].firsttarc==NULL>G.vertices[i].firsttarc=a;//當此弧是頂點i的第一條弧時else//當此弧不是頂點i的第一條弧時{a->nextrarc=G.vertices[i].firsttarc->nextrarc;G.vertices[i].firsttarc=a;}//處理另一條對稱的頂點jif<G.vertices[j].firsttarc==NULL>G.vertices[j].firsttarc=a;//當此弧是頂點j的第一條弧時else//當此弧不是頂點j的第一條弧時{a->nextrarc=G.vertices[j].firsttarc->nextrarc;G.vertices[j].firsttarc=a;}}returnok;}//有向網statuscreatedn<algraph&G>{cout<<"請輸入有向網的頂點數,弧數："<<endl;scanf<"%d%d",&G.vexnum,&G.arcnum>;cout<<"請輸入各頂點的值："<<endl;for<inti=0;i<G.vexnum;++i>scanf<"%d",&G.vertices[i].data>;//構造頂點for<inti=0;i<G.vexnum;++i>G.vertices[i].firsttarc=NULL;//初始化指針firsttarccout<<"請輸入成對的關系頂點數值以及其權值：〔形如：11221"<<endl;for<intk=0;k<G.arcnum;++k>{vertextypev1,v2;intw;scanf<"%d%d%d",&v1,&v2,&w>;getchar<>;inti=locatevex<G,v1>;intj=locatevex<G,v2>;arcnode*a;a=<arcnode*>malloc<sizeof<arcnode>>;if<a==NULL>exit<1>;<*a>.adjvex=j;<*a>.adj=w;<*a>.nextrarc=NULL;<*a>.info=NULL;if<G.vertices[i].firsttarc==NULL>G.vertices[i].firsttarc=a;//當此弧是頂點i的第一條弧時else//當此弧不是頂點i的第一條弧時連接到第一條弧位置,將原來的弧接到后面{a->nextrarc=G.vertices[i].firsttarc->nextrarc;G.vertices[i].firsttarc=a;}}returnok;}//無向圖statuscreateudg<algraph&G>{cout<<"請輸入無向圖的頂點數,弧數："<<endl;scanf<"%d%d",&G.vexnum,&G.arcnum>;getchar<>;cout<<"請輸入各頂點的值："<<endl;for<inti=0;i<G.vexnum;++i>{scanf<"%d",&G.vertices[i].data>;}//頂點賦值getchar<>;for<inti=0;i<G.vexnum;++i>G.vertices[i].firsttarc=NULL;//初始化指針firsttarccout<<"請輸入成對的關系頂點數值：〔形如：1122"<<endl;for<intk=0;k<G.arcnum;++k>{vertextypev1,v2;scanf<"%d%d",&v1,&v2>;getchar<>;inti=locatevex<G,v1>;intj=locatevex<G,v2>;arcnode*a;a=<arcnode*>malloc<sizeof<arcnode>>;//為加入的弧結點申請空間if<a==NULL>exit<1>;<*a>.adjvex=j;<*a>.adj=1;<*a>.nextrarc=NULL;<*a>.info=NULL;if<G.vertices[i].firsttarc==NULL>//當此弧是頂點i的第一條弧時{G.vertices[i].firsttarc=a;//cout<<"attachtofirsttarc"<<endl;}else//當此弧不是頂點i的第一條弧時{a->nextrarc=G.vertices[i].firsttarc;G.vertices[i].firsttarc=a;//cout<<"attachsuccessfully!"<<endl;}//處理對稱的另一個頂點if<G.vertices[j].firsttarc==NULL>//當此弧是頂點j的第一條弧時{G.vertices[j].firsttarc=a;//cout<<"attachtofirsttarc"<<endl;}else//當此弧不是頂點j的第一條弧時{a->nextrarc=G.vertices[j].firsttarc;G.vertices[j].firsttarc=a;//cout<<"attachsuccessfully!"<<endl;}}returnok;}statuscreatedg<algraph&G>{cout<<"請輸入無向圖的頂點數,弧數："<<endl;scanf<"%d%d",&G.vexnum,&G.arcnum>;getchar<>;cout<<"請輸入各頂點的值："<<endl;for<inti=0;i<G.vexnum;++i>{scanf<"%d",&G.vertices[i].data>;}//頂點賦值getchar<>;for<inti=0;i<G.vexnum;++i>G.vertices[i].firsttarc=NULL;//初始化指針firsttarccout<<"請輸入成對的關系頂點數值：〔形如：1122"<<endl;for<intk=0;k<G.arcnum;++k>{vertextypev1,v2;scanf<"%d%d",&v1,&v2>;getchar<>;inti=locatevex<G,v1>;intj=locatevex<G,v2>;arcnode*a;a=<arcnode*>malloc<sizeof<arcnode>>;//為加入的弧結點申請空間if<a==NULL>exit<1>;<*a>.adjvex=j;<*a>.adj=1;<*a>.nextrarc=NULL;<*a>.info=NULL;if<G.vertices[i].firsttarc==NULL>//當此弧是頂點i的第一條弧時{G.vertices[i].firsttarc=a;//cout<<"attachtofirsttarc"<<endl;}else//當此弧不是頂點i的第一條弧時{a->nextrarc=G.vertices[i].firsttarc;G.vertices[i].firsttarc=a;//cout<<"attachsuccessfully!"<<endl;}}returnok;}鄰接表存儲結構的額DFS非遞歸算法：//visit函數voidvisit<vertextypea>{printf<"--%d-",a>;}//DFSvoidDFS<algraphG,intv>{intvisitp[MAX_VERTEX_NUM];//訪問標記數組,sqstackS;initstack<S>;//建立存儲訪問過結點的棧for<inti=0;i<G.vexnum;i++>visitp[i]=FALSE;//將各頂點訪問標記均賦值為FALSEvisit<G.vertices[v].data>;visitp[v]=TRUE;push<S,G.vertices[v].data>;//訪問并入棧第一個頂點while<S.base!=S.top>//當棧不為空時進行遍歷{arcnode*p;intnum=0,temp=0,k=0,m=0;gettop<S,k>;//得到棧頂元素m=locatevex<G,k>;//定位棧頂元素在圖中的坐標for<p=G.vertices[m].firsttarc;p!=NULL;p=p->nextrarc>{if<visitp[<*p>.adjvex]==FALSE>num+=1;}//cout<<"thereare"<<num<<"pointleft"<<endl;if<num==0>//如果此頂點的后繼頂點都被訪問過,則從棧中刪除此頂點{pop<S,temp>;cout<<"nopointleft"<<endl;}else{for<p=G.vertices[m].firsttarc;p!=NULL;p=p->nextrarc>if<visitp[<*p>.adjvex]==FALSE>{visit<G.vertices[<*p>.adjvex].data>;visitp[<*p>.adjvex]=TRUE;push<S,G.vertices[<*p>.adjvex].data>;break;//因為是深度優先,所以遇到可訪問頂點并訪問后跳出for循環}}}destroystack<S>;//銷毀輔助棧}鄰接表存儲結構的DFS遞歸算法：intvisitp[MAX_VERTEX_NUM];//全局變量,//注意在main函數中都賦初值FALSEvoidvisit<vertextypea>{printf<"--%d-",a>;}voidDFS<algraphG,intv>{visit<G.vertices[v].data>;visitp[v]=TRUE;for<arcnode*p=G.vertices[v].firsttarc;p!=NULL;p=p->nextrarc>if<visitp[p->adjvex]==FALSE>DFS<G,p->adjvex>;}intmain<>{algraphG;createudg<G>;for<inti=0;i<MAX_VERTEX_NUM;i++>visitp[i]=FALSE;DFS<G,0>;return0;}鄰接表存儲結構的BFS非遞歸算法：voidvisit<vertextypea>{printf<"--%d-",a>;}voidBFS<algraphG,intv>{intvisitp[MAX_VERTEX_NUM];linkqueueQ;if<initqueue<Q>==1>for<inti=0;i<MAX_VERTEX_NUM;i++>visitp[i]=FALSE;elseexit<1>;//首先訪問第一個頂點visit<G.vertices[v].data>;visitp[v]=TRUE;enqueue<Q,G.vertices[v].data>;while<Q.front!=Q.rear>{intk=0,m=0,num=0,temp=0;gethead<Q,k>;m=locatevex<G,k>;//得到隊首元素并定位for<arcnode*j=G.vertices[m].firsttarc;j!=NULL;j=j->nextrarc>if<visitp[<*j>.adjvex]==FALSE>num+=1;if<num==0>dequeue<Q,temp>;//如果此頂點的后繼均訪問過,則從隊列中刪除else{for<arcnode*p=G.vertices[m].firsttarc;p!=NULL;p=p->nextrarc>if<visitp[<*p>.adjvex]==FALSE>{visit<G.vertices[<*p>.adjvex].data>;//執行visit操作visitp[<*p>.adjvex]=TRUE;//訪問標志置真enqueue<Q,G.vertices[<*p>.adjvex].data>;}}}destroyqueue<Q>;}intmain<>{algraphG;createudg<G>;BFS<G,0>;return0;}//鄰接表存儲結構的BFS遞歸算法voidvisit<vertextypea>{printf<"--%d-",a>;}intvisitp[MAX_VERTEX_NUM];voidBFS<algraphG,intv>{linkqueueQ;initqueue<Q>;if<visitp[v]==FALSE>{visit<G.vertices[v].data>;visitp[v]=TRUE;}//訪問標記,inte;intaddress;arcnode*p;for<p=G.vertices[v].firsttarc;p!=NULL;p=p->nextrarc>if<visitp[<*p>.adjvex]==FALSE>{visit<G.vertices[<*p>.adjvex].data>;visitp[<*p>.adjvex]=TRUE;enqueue<Q,G.vertices[<*p>.adjvex].data>;}//訪問該與結點有關系的全部結點while<Q.front!=Q.rear>{dequeue<Q,e>;address=locatevex<G,e>;BFS<G,address>;//遞歸調用BFS}destroyqueue<Q>;}intmain<>{algraphG;createudg<G>;inti;for<i=0;i<MAX_VERTEX_NUM;i++>visitp[i]=FALSE;BFS<G,0>;return0;}輔助隊列的實現：#include<iostream>#include<string.h>#include<stdio.h>#include<stdlib.h>#include<malloc.h>typedefintvertextype;typedefintinfotype;typedefintstatus;typedefintqelemtype;#defineerror0#defineok1#defineINFINTYINT_MAX//最大值∞#defineMAX_VERTEX_NUM20//最大定點個數#defineoverflow-2#defineFALSE0#defineTRUE1usingnamespacestd;typedefstructqnode{qelemtypedata;structqnode*next;}qnode,*queueptr;typedefstruct{queueptrfront;//隊頭指針queueptrrear;//隊尾指針}linkqueue;statusinitqueue<linkqueue&Q>;statusgethead<linkqueueQ,qelemtype&e>;statusenqueue<linkqueue&Q,qelemtypee>;statusdequeue<linkqueue&Q,qelemtype&e>;statusdestroyqueue<linkqueue&Q>;statusinitqueue<linkqueue&Q>{Q.front=Q.rear=<queueptr>malloc<sizeof<qnode>>;if<!Q.front>exit<overflow>;Q.front->next=NULL;returnok;}statusgethead<linkqueueQ,qelemtype&e>{if<Q.front==Q.rear>returnerror;e=Q.front->next->data;returnok;}statusenqueue<linkqueue&Q,qelemtypee>{queueptrp;p=<queueptr>mal