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

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