圖的基本操作與實現(xiàn)

1、摘要：圖（Graph）是一種非線性結(jié)構(gòu)，它的每一個頂點可以與多個其它頂點相關(guān)聯(lián)，各頂點之間的關(guān)系是任意的。這種結(jié)構(gòu)的靈活性很強，可以用來描述和求解更多的實際問題，因此得到廣泛的應(yīng)用。最典型的應(yīng)用領(lǐng)域有電路分析、尋找最短路線、項目規(guī)劃、鑒別化合物、統(tǒng)計力學(xué)、遺傳學(xué)、控制論、語言學(xué)，以及一些社會科學(xué)中。反過來，也正是由于其限制很少，已不再屬于線性結(jié)構(gòu)，因此運用這類結(jié)構(gòu)時需要有更多的技巧。本課題是在VC+環(huán)境下，運用圖的性質(zhì)完成各種基本操作的實現(xiàn)。關(guān)鍵詞：鄰接矩陣；鄰接表；深度（廣度）優(yōu)先遍歷；連通分量；遞歸目錄TOC o 1-5 h z HYPERLINK l bookmark2 1需求分析1 H

2、YPERLINK l bookmark4 1.1課程設(shè)計題目1 HYPERLINK l bookmark6 1.2課程設(shè)計任務(wù)及要求1 HYPERLINK l bookmark8 1.3課程設(shè)計思想1 HYPERLINK l bookmark10 2概要設(shè)計2 HYPERLINK l bookmark12 2.1程序的整體功能結(jié)構(gòu)2 HYPERLINK l bookmark14 2.2數(shù)據(jù)結(jié)構(gòu)的設(shè)計3 HYPERLINK l bookmark20 詳細設(shè)計和實現(xiàn)5 HYPERLINK l bookmark22 3.1算法流程圖5 HYPERLINK l bookmark24 3.2各個要求的實

3、現(xiàn)方法5 HYPERLINK l bookmark28 3.3主程序設(shè)計7 HYPERLINK l bookmark30 調(diào)試與操作說明20 HYPERLINK l bookmark32 4.1程序調(diào)試與體會204.2程序運行結(jié)果21總結(jié)23致謝24參考文獻25 1需求分析1.1課程設(shè)計題目自選存儲結(jié)構(gòu)，輸入含n個頂點(用字符表示頂點)和e條邊的圖G；求每個頂點的度,輸出結(jié)果；指定任意頂點x為初始頂點，對圖G作DFS遍歷，輸出DFS頂點序列(提示:使用一個棧實現(xiàn)DFS)；指定任意頂點x為初始頂點，對圖G作BFS遍歷，輸出BFS頂點序列(提示:使用一個隊列實現(xiàn)BFS)；輸入頂點x,查找圖G:若存

4、在含x的頂點，則刪除該結(jié)點及與之相關(guān)連的邊，并作DFS遍歷(執(zhí)行操作3)；否則輸出信息“無x”判斷圖G是否是連通圖，輸出信息“YES”/“NO”；如果選用的存儲結(jié)構(gòu)是鄰接矩陣，則用鄰接矩陣的信息生成圖G的鄰接表，即復(fù)制圖G然再執(zhí)行操作(2)；反之亦然。1.2課程設(shè)計任務(wù)及要求搜集圖方面的資料；負責(zé)設(shè)計數(shù)據(jù)結(jié)構(gòu)，畫好流程圖，編寫代碼；撰寫課程設(shè)計報告；參加答辯。1.3課程設(shè)計思想1.3.1圖的鄰接表表示在第i行的單鏈表中，各結(jié)點分別存放與同一個頂點vi關(guān)聯(lián)的各條邊。各結(jié)點配有標識dest，指示該邊的另一個頂點；還配有指針link，指向同一鏈表中的下一條邊的邊結(jié)點。對于帶權(quán)圖，結(jié)點中還要保存該邊的

5、權(quán)值cost。通過在頂點表的第i個頂點信息中保存的指針adj,可以找到與頂點i對應(yīng)的邊鏈表的第一個邊結(jié)點；此外，該記錄還保存有該頂點的其他信息。1.3.2圖的深度優(yōu)先搜索深度優(yōu)先搜索是個不斷探查和回溯的過程。在探查的每一步,算法都有一個當(dāng)前頂點。最初的當(dāng)前頂點,也就是指定的起始頂點。每一步探查過程中,首先對當(dāng)前頂點v進行訪問,并立即設(shè)置該頂點的訪問標志visitedv=true。接著在v的所有鄰接頂點中，找出尚未訪問過的一個，將其作為下一步探查的當(dāng)前頂點。倘若當(dāng)前頂點的所有鄰接頂點都已經(jīng)被訪問過，則退回一步，將前一步所訪問的頂點重新取出，當(dāng)作探查的當(dāng)前頂點。重復(fù)上述過程，直到最初指定起始頂點的

6、所有鄰接頂點都被訪問到，此時連通圖中的所有頂點也必然都被訪問過了。1.3.3圖的廣度優(yōu)先搜索廣度優(yōu)先搜索時一個逐層遍歷的過程，在此過程中，圖中有多少頂點就要重復(fù)多少步。每一步都有一個當(dāng)前頂點。最初的當(dāng)前頂點是主過程指定的起始頂點。在每一步中，首先訪問當(dāng)前頂點V，并設(shè)置該頂點的訪問標志visitedv=true。接著依次訪問v的各個未曾被訪問過的鄰接頂點wl,w2,，wt，然后再順序訪問wl，w2，wt的所有還未被訪問過的鄰接頂點。再從這些訪問過的頂點出發(fā)，再訪問它們的所有還未被訪問過的鄰接頂點，如此做下去，直到圖中所有頂點都被訪問為止。2概要設(shè)計2.1程序的整體功能結(jié)構(gòu)輸入1個圖先求出每個頂點

7、的度，輸出結(jié)果;然后指定任意頂點x為初始頂點，對圖G作DFS遍歷，輸出DFS頂點序列；接著指定任意頂點x為初始頂點，對圖G作BFS遍歷，輸出BFS頂點序列；其次輸入頂點x,查找圖G:若存在含x的頂點，則刪除該結(jié)點及與之相關(guān)連的邊，并作DFS遍歷（執(zhí)行操作3）；否則輸出信息“無x”；下一步是判斷圖G是否是連通圖，輸出信息“YES”/“NO囁后如果選用的存儲結(jié)構(gòu)是鄰接矩陣，則用鄰接矩陣的信息生成圖G的鄰接表，即復(fù)制圖G,然再執(zhí)行操作(2)；反之亦然。2.2數(shù)據(jù)結(jié)構(gòu)的設(shè)計2.2.1邊節(jié)點類的定義structEdge/邊結(jié)點的定義intdest;/邊的另一頂點位置Ecost;/邊上的權(quán)值Edge*li

8、nk;/下一條邊鏈指針;2.2.2頂點類的定義templatevclassT,classE/頂點的定義structVertexTdata;/頂點的名字Edge*adj;/邊鏈表的頭指針;2.2.3圖類的定義templateclassGraph/圖的類定義protected:intmaxVertices;/圖中最大的頂點數(shù)intnumEdges;/當(dāng)前邊數(shù)intnumVertices;/當(dāng)前頂點數(shù)T*output;/存放遍歷的數(shù)組T*input;/存放輸入數(shù)組VertexvT,E*NodeTable;/頂點表(各邊鏈表的頭結(jié)點)intgetVertexPos(constTvertx)/取頂點v在

9、數(shù)組中的位置intj=-1;for(inti=0;inumVertices;i+)if(NodeTablei.data=vertx)j=i;returnj;voidDFS(Graph&G,intv,boolvisited)/圖的深度優(yōu)先搜索coutG.getValue(v)=0&i&G,constT&v);/從頂點v出發(fā)對圖G進行深度優(yōu)先遍歷的主過程intBFS(Graph&G,constT&v);/圖的廣度優(yōu)先搜索voidWheCan(GraphvT,E&G);/判斷是否為連通圖voidOutPut();輸出voidHaveEdge(GraphvT,E&G);/求頂點的度voidSerach

10、Vertex(GraphvT,E&G);/輸入頂點x,查找圖G:若存在含x的頂點，則刪除該結(jié)點及與之相關(guān)連的邊，并作DFS遍歷voidChangeGraph(Graph&G);/將用鄰接表表示的數(shù)轉(zhuǎn)換為鄰接矩陣表示voidInput();/輸入;3詳細設(shè)計和實現(xiàn)3.1算法流程圖程序主要設(shè)計了六個功能：首先是求每個頂點的度，然后可以選擇對圖G作DFS（或BFS）搜索，接著可以判斷此圖是否連通，接著可以將圖G轉(zhuǎn)換為臨街矩陣存儲方式退出，最后可以對圖G作查找頂點。主函數(shù)流程如下：圖3.1.1主函數(shù)流程圖3.2各個要求的實現(xiàn)方法3.2.1自選存儲結(jié)構(gòu)，輸入含n個頂點（用字符表示頂點）和e條邊的圖G采用

11、鄰接表的存儲結(jié)構(gòu)N個頂點的輸入存儲到頂點節(jié)點鏈表（Vertex）中如果第n個節(jié)點和第m個節(jié)點之間含有一條邊e,就將n和m的頂點鏈表中指向的邊鏈表中存儲入n和m在頂點表中的下標和權(quán)值3.2.2求每個頂點的度,輸出結(jié)果頂點的度指與該頂點相關(guān)聯(lián)的邊的條數(shù)在用鄰接鏈表做為圖的存儲方式中，要求一個頂點n的度只要去搜索存放頂點n的邊節(jié)點鏈表,其中存放了多少條邊的信息,這個頂點的度就為多少。3.2.3指定任意頂點x為初始頂點時圖G作DFS遍歷，輸出DFS頂點序列DFS遍歷指的是深度優(yōu)先搜索深度優(yōu)先搜索的基本思想：DFS在訪問圖中某一起始頂點v后,由v出發(fā),訪問它的任一鄰接頂點w1;再從w1出發(fā),訪問與w1鄰

12、接但還沒有訪問過的頂點w2;然后再從w2出發(fā),進行類似的訪問,如此進行下去,直至到達所有的鄰接頂點都被訪問過的頂點u為止。接著,退回一步,退到前一次剛訪問過的頂點,看是否還有其它沒有被訪問的鄰接頂點。如果有,則訪問此頂點,之后再從此頂點出發(fā),進行與前述類似的訪問;如果沒有,就再退回一步進行搜索。重復(fù)上述過程,直到連通圖中所有頂點都被訪問過為止。3.2.4指定任意頂點x為初始頂點時圖G作BFS遍歷，輸出BFS頂點序列BFS指的是廣度優(yōu)先搜索BFS基本思想：BFS在訪問了起始頂點v之后,由v出發(fā),依次訪問v的各個未被訪問過的鄰接頂點w1,w2,wt,然后再順序訪問w1,w2,wt的所有還未被訪問過

13、的鄰接頂點。再從這些訪問過的頂點出發(fā)，再訪問它們的所有還未被訪問過的鄰接頂點，如此做下去，直到圖中所有頂點都被訪問到為止。廣度優(yōu)先搜索是一種分層的搜索過程,每向前走一步可能訪問一批頂點,不像深度優(yōu)先搜索那樣有往回退的情況。因此,廣度優(yōu)先搜索不是一個遞歸的過程。3.2.5輸入頂點x,查找圖G:若存在含x的頂點，則刪除該結(jié)點及與之相關(guān)連的邊，并作DFS遍歷（執(zhí)行操作3）；否則輸出信息“無x”；輸入頂點，在頂點表中所搜是否含有這個頂點，如果沒有，就輸出“無X”如果含有，搜索存放頂點n的邊節(jié)點鏈表，找出其中存放的頂點m,然后將這個頂點m鏈表中的存放n的那個節(jié)點刪除，同時將n中存放m的節(jié)點刪除。然后在頂

14、點鏈表中存放頂點n的節(jié)點刪除。3.2.6判斷圖G是否是連通圖，輸出信息“YES”/“NO”；對圖做BFS遍歷，如果遍歷到的頂點數(shù)等于當(dāng)前的頂點數(shù)的個數(shù)，這個圖就是聯(lián)通圖，反之就不是連通圖3.2.7如果選用的存儲結(jié)構(gòu)是鄰接矩陣,則用鄰接矩陣的信息生成圖G的鄰接表，即復(fù)制圖G,然再執(zhí)行操作；反之亦然我采用的是鄰接矩陣做為圖的存儲結(jié)構(gòu)。將用鄰接表存儲的圖轉(zhuǎn)化為鄰接矩陣的存儲的基本思想是：（1）將圖的頂點表中存放的頂點的信息都存放在一個頂點矩陣中（2）逐個搜索各個頂點的邊節(jié)點鏈表，如果含有節(jié)點，將鄰接矩陣中對應(yīng)二維數(shù)組的值賦值為cost的值。頂點的度為：統(tǒng)計第i行（列）不為o的個數(shù)可得頂點i的度。3.

15、3主程序設(shè)計/Graph.h#include#include#includeQueue.husingnamespacestd;templatestructEdge/邊結(jié)點的定義/邊的另一頂點位置/邊上的權(quán)值/下一條邊鏈指針/構(gòu)造函數(shù)intdest;Ecost;Edge*link;/構(gòu)造函數(shù)Edge()Edge(intnum,Ecost):dest(num),weight(cost),link(NULL)booloperator!=(Edge&R)const/判邊等否returndest!=R.dest;templatevclassT,classE頂點的定義structVertexTdata;/

16、頂點的名字Edge*adj;/邊鏈表的頭指針;templateclassGraph/圖的類定義protected:intmaxVertices;/圖中最大的頂點數(shù)intnumEdges;/當(dāng)前邊數(shù)intnumVertices;/當(dāng)前頂點數(shù)T*output;/存放遍歷的數(shù)組T*input;/存放輸入數(shù)組VertexvT,E*NodeTable;/頂點表(各邊鏈表的頭結(jié)點)intgetVertexPos(constTvertx)/取頂點v在數(shù)組中的位置intj=-1;for(inti=0;inumVertices;i+)if(NodeTablei.data=vertx)j=i;returnj;vo

17、idDFS(Graph&G,intv,boolvisited)/圖的深度優(yōu)先搜索coutG.getValue(v)=0&i&QconstT&v);/從頂點v出發(fā)對圖G進行深度優(yōu)先遍歷的主過程intBFS(GraphvT,E&G,constT&v)圖的廣度優(yōu)先搜索voidWheCan(GraphvT,E&G);判斷是否為連通圖voidOutPut();輸出voidHaveEdge(GraphvT,E&G);求頂點的度voidSerachVertex(GraphvT,E&G);/輸入頂點x,查找圖G:若存在含x的頂點,則刪除該結(jié)點及與之相關(guān)連的邊，并作DFS遍歷voidChangeGraph(Gr

18、aph&G);/將用鄰接表表示的數(shù)轉(zhuǎn)換為鄰接矩陣表示voidInput();/輸入;#includetemplateGraph:Graph()/構(gòu)造函數(shù)：建立一個空的鄰接表maxVertices=100;numVertices=0;numEdges=0;NodeTable=newVertexmaxVertices;/創(chuàng)建頂點表數(shù)組if(NodeTable=NULL)cerrvv存儲分配錯!vvendl;exit(1);for(inti=0;imaxVertices;i+)NodeTablei.adj=NULL;output=newTmaxVertices;templateGraphvT,E:G

19、raph()/析構(gòu)函數(shù)：刪除一個鄰接表for(inti=0;inumVertices;i+)Edge*p=NodeTablei.adj;while(p!=NULL)NodeTablei.adj=p-link;deletep;p=NodeTablei.adj;deleteNodeTable;/刪除頂點表數(shù)組templateboolGraph:insertVertex(constT&vertex)/插入頂點if(numVertices=maxVertices)returnfalse;NodeTablenumVertices.data=vertex;numVertices+;returntrue;t

20、emplateboolGraphvT,E:insertEdge(intvl,intv2,Ecost)/插入邊(vl,v2),權(quán)值為costif(vl=0&vl=0&v2=numVertices)Edge*q,*p=NodeTablevl.adj;/vl對應(yīng)的邊鏈表頭z指針while(p!=NULL&p-dest!=v2)/尋找鄰接頂點v2p=p-link;if(p!=NULL)/找到此邊不插入returnfalse;p=newEdge;/否則創(chuàng)建新節(jié)點q=newEdge;p-dest=v2;p-cost=cost;p-link=NodeTablev1.adj;鏈入v1的邊鏈表NodeTable

21、vl.adj=p;q-dest=v1;q-cost=cost;q-link=NodeTablev2.adj;鏈入v2的邊鏈表NodeTablev2.adj=q;numEdges+;returntrue;elsecerrvv參數(shù)有誤!請重新輸入!vvendl;exit(1);returnfalse;templateboolGraph:removeVertex(intv)if(numVertices=1|v=numVertices)cerrvv參數(shù)有誤，請重新輸入！vvendl;exit(1);returnfalse;/表空或頂點超出范圍EdgevT,E*p,*s,*t;intk;while(No

22、deTablev.adj!=NULL)p=NodeTablev.adj;k=p-dest;s=NodeTablek.adj;t=NULL;while(s!=NULL&s-dest!=v)t=s;s=s-link;if(s!=NULL)if(t=NULL)NodeTablek.adj=s-link;elset-link=s-link;deletes;NodeTablev.adj=p-link;deletep;numEdges-;numVertices-;NodeTablev.data=NodeTablenumVertices.data;p=NodeTablev.adj=NodeTablenumV

23、ertices.adj;while(p!=NULL)s=NodeTablep-dest.adj;while(s!=NULL)if(s-dest=numVertices)s-dest=v;break;elses=s-link;returntrue;templateboolGraph:removeEdge(intv1,intv2)if(v1!=-1&v2!=-1)Edge*p=NodeTablev1.adj,*q=NULL,*s=p;while(p!=NULL&p-dest!=v2)q=p;p=p-link;if(p!=NULL)if(p=s)NodeTablev1.adj=p-link;else

24、q-link=p-link;deletep;elsereturnfalse;p=NodeTablev2.adj;q=NULL;s=p;while(p-dest!=v1)q=p;p=p-link;if(p=s)NodeTablev2.adj=p-link;elseq-link=p-link;deletep;returntrue;returnfalse;templateintGraphvT,E:getFirstNeighbor(intv)給出頂點位置為v的第一個鄰接頂點的位置,如果找不到,則函數(shù)返回-1f(v!=-l)頂點v存在Edge*p=NodeTablev.adj;/對應(yīng)邊鏈表第一個邊結(jié)點i

25、f(p!=NULL)/存在,返回第一個鄰接頂點returnp-dest;return-l;/第一個鄰接頂點不存在templateintGraphvT,E:getNextNeighbor(intv,intw)/給出頂點v的鄰接頂點w的下一個鄰接頂點的位置，若沒有下一個鄰接頂點，則函數(shù)返回-1if(v!=-1)頂點v存在Edge*p=NodeTablev.adj;while(p!=NULL&p-dest!=w)p=p-link;if(p!=NULL&p-link!=NULL)/返回下一個鄰接頂點returnp-link-dest;return-1;/下一鄰接頂點不存在templateintGrap

26、hvT,E:getFirstCost(intv)/給出頂點位置為v的第一個鄰接頂點的位置,如果找不到,則函數(shù)返回-1if(v!=-1)頂點v存在Edge*p=NodeTablev.adj;/對應(yīng)邊鏈表第一個邊結(jié)點的cost值if(p!=NULL)/存在,返回第一個鄰接頂點returnp-cost;return-1;/第一個鄰接頂點不存在templateintGraphvT,E:getNextCost(intv,intw)/給出頂點v的鄰接頂點w的下一個鄰接頂點的位置,若沒有下一個鄰接頂點,則函數(shù)返回-1if(v!=-1)/頂點v存在Edge*p=NodeTablev.adj;while(p!=

27、NULL&p-dest!=w)p=p-link;if(p!=NULL&p-link!=NULL)/返回下一個鄰接頂點的cost值returnp-link-cost;return-1;/下一鄰接頂點不存在/下一鄰接頂點不存在templatevoidGraph:DFS(Graph&G,constT&v)inti,loc,n=numVertices;/頂點個數(shù)bool*visited=newbooln;/創(chuàng)建輔助數(shù)組for(i=0;in;i+)/輔助數(shù)組visited初始化visitedi=false;loc=v;DFS(G,loc,visited);/從頂點0開始深度優(yōu)先搜索deletevisit

28、ed;templateintGraph:BFS(Graph&G,constT&v)inti,w,n=numVertices,m=0;/圖中頂點個數(shù)bool*visited=newbooln;for(i=0;in;i+)visitedi=false;intloc=v;/取頂點號outputm=G.getValue(loc);/訪問頂點vvisitedloc=true;/做已訪問標記QueueQ(20);Q.EnQueue(loc);/頂點進隊列while(!Q.IsEmpty()/循環(huán),訪問所有結(jié)點Q.DeQueue(loc);w=G.getFirstNeighbor(loc);/第一個鄰接頂點

29、while(w!=-1)/若鄰接頂點w存在if(!visitedw)/若未訪問過output+m=G.getValue(w);/訪問visitedw=true;Q.EnQueue(w);/頂點w進隊列 # w=G.getNextNeighbor(loc,w);/找頂點loc的下一個鄰接頂點/外層循環(huán)，判隊列空否deletevisited;returnm;templatevoidGraph:WheCan(Graph&G)/判斷是否為連通圖intx=0;x=BFS(G,0);if(x=numVertices)coutYESendl;elsecoutNOendl;templatevoidGraph:

30、OutPut()for(inti=0;inumVertices;i+)coutoutputi;coutendl;template/得到每個頂點的度voidGraph:HaveEdge(Graph&G)for(inti=0;inumVertices;i+)intn=0;intm=getFirstNeighbor(i);if(m!=-1)n+;inta=getNextNeighbor(i,m);if(a!=-1)don+;a=getNextNeighbor(i,a);while(a=!-1);coutvv頂點vvgetValue(i)vv的度為：vvnvvendl;templatevoidGrap

31、hvT,E:SerachVertex(GraphvT,E&G)輸入頂點x,查找圖G:若存在含x的頂點，則刪除該結(jié)點及與之相關(guān)連的邊，并作DFS遍歷Tver;T*n=newTnumVertices;inti,m=0;inta;coutvv請輸入要查詢的定點的數(shù)值!vvendl;cinver;i=getVertexPos(ver);if(i=-1)coutvv你要查找的頂點不存在vvendl;elsenm=getFirstNeighbor(i);a=nm;m+;if(getNextNeighbor(i,nm)!=-1)nm=getNextNeighbor(i,a);a=nm;m+;for(intj

32、=0;jvm+1;j+)removeEdge(i,nj);coutvv刪除vvvervv的頂點后做DFS遍歷后為:vvendl;DFS(G,0);templatevclassT,classEvoidGraphvT,E:ChangeGraph(GraphvT,E&G)inti,j,m;T*VerticesList=newTnumVertices;/頂點表for(i=0;ivnumVertices;i+)VerticesListi=getValue(i);E*Edge=(E*)newE*numVertices;/鄰接矩陣for(i=0;ivnumVertices;i+)Edgei=newEnumV

33、ertices;for(i=0;inumVertices;i+)for(j=0;jvnumVertices;j+)/鄰接矩鎮(zhèn)初始化Edgeij=0;for(i=0;inumVertices;i+)intm=getFirstNeighbor(i);if(m!=-1)Edgeim=Edgemi=getFirstCost(i);inta=getNextNeighbor(i,m);if(a!=-1)Edgeia=Edgeai=getNextCost(i,m);a=getNextNeighbor(i,a);coutvv鄰接矩陣為：vvendl;for(i=0;ivoidGraphvT,E:Input()

34、inti,j;intnumv,nume;input=newT100;inta,b,c;coutvv請輸入頂點總數(shù)和邊的總數(shù)!vvendl;cinnumvnume; for(i=0;iinputi;for(i=0;ivnumv;i+)insertVertex(inputi);for(j=0;jvnume;j+)coutvv請輸入要插入邊的兩個頂點和權(quán)值！vvendl;cinabc;insertEdge(a,b,c);deleteinput;/Queue.htemplatevclassTclassQueue/隊列抽象類protected:intrear,front;T*elements;intma

35、xSize;public:Queue()Queue(intsz);Queue()/隊尾與隊頭指針/隊列存放數(shù)組/隊列最大容量/構(gòu)造函數(shù)/析構(gòu)函數(shù)boolEnQueue(Tx);boolDeQueue(T&x);boolgetFront(T&x);boolIsEmpty()const/進隊列/出隊列/取隊頭/判隊列空return(front=rear)?true:false;boolIsFull()constreturn(rear+1)%maxSize=front)?true:false;templatevclassTQueuevT:Queue(intsz):front(0),rear(O),m

36、axSize(sz)構(gòu)造函數(shù)/判隊列滿elements=newTmaxSize;templateboolQueue:EnQueue(Tx)/入隊操作，若隊列不滿,則x入隊,否則返回falseif(IsFull()=true)returnfalse;elementsrear=x;/先存入rear=(rear+1)%maxSize;/尾指針后移returntrue;templateboolQueuevT:DeQueue(T&x)出隊操作，若隊列不空則退隊頭元素并返回其值if(IsEmpty()=true)returnfalse;x=elementsfront;/先取隊頭front=(front+1

37、)%maxSize;/再隊頭指針加一returntrue;/main.cpp#include#includeGraph.h#includeusingnamespacestd;intmain()intf=0,m;GraphG;coutsetw(60)|1.輸入圖G|endl;coutsetw(60)|2.求每個頂點的度|endl;coutvvsetw(60)vvl3.對圖G作DFS搜索lvvendl;coutvvsetw(60)vvl4.對圖G作BFS搜索lvvendl;coutsetw(60)|5.判斷圖G是否是連通圖|endl;coutvvsetw(60)vvl6.將圖G轉(zhuǎn)換為臨街矩陣存儲方

38、式lvvendl;coutsetw(60)|7.對圖G作查找頂點|endl;coutsetw(60)|8.退出程序|endl;coutsetw(60)|f;if(f=1)G.Input();if(f=2)G.HaveEdge(G);if(f=3)coutvv請輸入要開始搜索的頂點的下標：vvendl;cinm;coutvvDFS搜索的結(jié)果為：;G.DFS(G,m);coutvvendl;if(f=4)coutvv請輸入要開始搜索的頂點的下標：vvendl;cinm;coutvvBFS搜索的結(jié)果為：;G.BFS(G,m);G.OutPut();if(f=5)G.WheCan(G);if(f=6)

39、G.ChangeGraph(G);if(f=7)G.SerachVertex(G);while(f!=8);return0;4調(diào)試與操作說明4.1程序調(diào)試與體會從一定程度上說，編一個程序并不難，難的是要把這個程序完全調(diào)試正確，但是不可能把程序的每一條執(zhí)行路徑都執(zhí)行一遍。也就是說，不可能保證我們的程序是百分之百的正確的。我們調(diào)試的目的是在程序沒有語法錯誤的基礎(chǔ)上保證我們的程序能達到我們所需要的主要的功能。我們在調(diào)試前應(yīng)該要先明白我們要輸入些什么數(shù)據(jù)并且其應(yīng)該得到些什么樣的結(jié)果，這樣我們才能更早的查找出錯 誤并成功調(diào)試出結(jié)果。4.2程序運行結(jié)果|洼輔入F連蟆咋LIw碼！3請輸入要幵始搜索的頂點的下

40、標:1搜索的結(jié)果為：生32351恫輸入你要操作的號碼！1請輸入要開始僅索的頂點的下標;2搜索的結(jié)果為:542343幃輸入你要操作的號碼！5JH:卜輔厶詠要摂詐眄三碼！鄰接炬陣為:UJ孑no00頂點2的度為2頂點燈的度為1頂點54的度為1請輸入你要操柞的號碼！r諸帝;、.尖查瑜i(n定蠱前救世！!k刪除54的頂點后做DFS遍歷后対:2343請嶽扎你要操作的號碼通過此次課程設(shè)計，我明白了很多東西，更加了解了本學(xué)期所學(xué)的內(nèi)容。由于之前對VC+的知識沒有足夠的掌握，使我在實驗的最初階段遇到了不小的困難，但是隨著實驗的進行，隨著問題的一步步被我解決了，我由衷的感到高興，因為我又掌握了一些知識：知道圖可以用鄰接表存儲，明白如何對圖進行深度（廣度）優(yōu)先搜索遍歷等。在剛剛結(jié)束的一個學(xué)期里，我對數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)才僅僅是個入門，通過這次的課程設(shè)計，我才發(fā)現(xiàn)自己在以往學(xué)習(xí)中的諸多問題，比如對圖的學(xué)習(xí)不夠深入，對于同一問題沒有多角度的思考，僅僅局限于一種方法，根本沒有思考是否還有別的更簡單更快捷的方法，不能做