數(shù)據(jù)結(jié)構(gòu)圖的遍歷實驗報告

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