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

1、摘要：圖（Graph）是一種非線性結(jié)構(gòu)，它的每一個(gè)頂點(diǎn)可以與多個(gè)其它頂點(diǎn)相關(guān)聯(lián)，各頂點(diǎn)之間的關(guān)系是任意的。這種結(jié)構(gòu)的靈活性很強(qiáng)，可以用來描述和求解更多的實(shí)際問題，因此得到廣泛的應(yīng)用。最典型的應(yīng)用領(lǐng)域有電路分析、尋找最短路線、項(xiàng)目規(guī)劃、鑒別化合物、統(tǒng)計(jì)力學(xué)、遺傳學(xué)、控制論、語言學(xué)，以及一些社會(huì)科學(xué)中。反過來，也正是由于其限制很少，已不再屬于線性結(jié)構(gòu)，因此運(yùn)用這類結(jié)構(gòu)時(shí)需要有更多的技巧。本課題是在VC+環(huán)境下，運(yùn)用圖的性質(zhì)完成各種基本操作的實(shí)現(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è)計(jì)題目1 HYPERLINK l bookmark6 1.2課程設(shè)計(jì)任務(wù)及要求1 HYPERLINK l bookmark8 1.3課程設(shè)計(jì)思想1 HYPERLINK l bookmark10 2概要設(shè)計(jì)2 HYPERLINK l bookmark12 2.1程序的整體功能結(jié)構(gòu)2 HYPERLINK l bookmark14 2.2數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)3 HYPERLINK l bookmark20 詳細(xì)設(shè)計(jì)和實(shí)現(xiàn)5 HYPERLINK l bookmark22 3.1算法流程圖5 HYPERLINK l bookmark24 3.2各個(gè)要求的實(shí)

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

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

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

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

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

8、nk;/下一條邊鏈指針;2.2.2頂點(diǎn)類的定義templatevclassT,classE/頂點(diǎn)的定義structVertexTdata;/頂點(diǎn)的名字Edge*adj;/邊鏈表的頭指針;2.2.3圖類的定義templateclassGraph/圖的類定義protected:intmaxVertices;/圖中最大的頂點(diǎn)數(shù)intnumEdges;/當(dāng)前邊數(shù)intnumVertices;/當(dāng)前頂點(diǎn)數(shù)T*output;/存放遍歷的數(shù)組T*input;/存放輸入數(shù)組VertexvT,E*NodeTable;/頂點(diǎn)表(各邊鏈表的頭結(jié)點(diǎn))intgetVertexPos(constTvertx)/取頂點(diǎn)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);/從頂點(diǎn)v出發(fā)對圖G進(jìn)行深度優(yōu)先遍歷的主過程intBFS(Graph&G,constT&v);/圖的廣度優(yōu)先搜索voidWheCan(GraphvT,E&G);/判斷是否為連通圖voidOutPut();輸出voidHaveEdge(GraphvT,E&G);/求頂點(diǎn)的度voidSerach

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

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

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

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

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

15、3主程序設(shè)計(jì)/Graph.h#include#include#includeQueue.husingnamespacestd;templatestructEdge/邊結(jié)點(diǎn)的定義/邊的另一頂點(diǎn)位置/邊上的權(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頂點(diǎn)的定義structVertexTdata;/

16、頂點(diǎn)的名字Edge*adj;/邊鏈表的頭指針;templateclassGraph/圖的類定義protected:intmaxVertices;/圖中最大的頂點(diǎn)數(shù)intnumEdges;/當(dāng)前邊數(shù)intnumVertices;/當(dāng)前頂點(diǎn)數(shù)T*output;/存放遍歷的數(shù)組T*input;/存放輸入數(shù)組VertexvT,E*NodeTable;/頂點(diǎn)表(各邊鏈表的頭結(jié)點(diǎn))intgetVertexPos(constTvertx)/取頂點(diǎn)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);/從頂點(diǎn)v出發(fā)對圖G進(jìn)行深度優(yōu)先遍歷的主過程intBFS(GraphvT,E&G,constT&v)圖的廣度優(yōu)先搜索voidWheCan(GraphvT,E&G);判斷是否為連通圖voidOutPut();輸出voidHaveEdge(GraphvT,E&G);求頂點(diǎn)的度voidSerachVertex(GraphvT,E&G);/輸入頂點(diǎn)x,查找圖G:若存在含x的頂點(diǎn),則刪除該結(jié)點(diǎn)及與之相關(guān)連的邊，并作DFS遍歷voidChangeGraph(Gr

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

19、raph()/析構(gòu)函數(shù)：刪除一個(gè)鄰接表for(inti=0;inumVertices;i+)Edge*p=NodeTablei.adj;while(p!=NULL)NodeTablei.adj=p-link;deletep;p=NodeTablei.adj;deleteNodeTable;/刪除頂點(diǎn)表數(shù)組templateboolGraph:insertVertex(constT&vertex)/插入頂點(diǎn)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)/尋找鄰接頂點(diǎn)v2p=p-link;if(p!=NULL)/找到此邊不插入returnfalse;p=newEdge;/否則創(chuàng)建新節(jié)點(diǎn)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;/表空或頂點(diǎn)超出范圍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)給出頂點(diǎn)位置為v的第一個(gè)鄰接頂點(diǎn)的位置,如果找不到,則函數(shù)返回-1f(v!=-l)頂點(diǎn)v存在Edge*p=NodeTablev.adj;/對應(yīng)邊鏈表第一個(gè)邊結(jié)點(diǎn)i

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

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

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

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

29、while(w!=-1)/若鄰接頂點(diǎn)w存在if(!visitedw)/若未訪問過output+m=G.getValue(w);/訪問visitedw=true;Q.EnQueue(w);/頂點(diǎn)w進(jìn)隊(duì)列 # w=G.getNextNeighbor(loc,w);/找頂點(diǎn)loc的下一個(gè)鄰接頂點(diǎn)/外層循環(huán)，判隊(duì)列空否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/得到每個(gè)頂點(diǎn)的度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頂點(diǎn)vvgetValue(i)vv的度為：vvnvvendl;templatevoidGrap

31、hvT,E:SerachVertex(GraphvT,E&G)輸入頂點(diǎn)x,查找圖G:若存在含x的頂點(diǎn)，則刪除該結(jié)點(diǎn)及與之相關(guān)連的邊，并作DFS遍歷Tver;T*n=newTnumVertices;inti,m=0;inta;coutvv請輸入要查詢的定點(diǎn)的數(shù)值!vvendl;cinver;i=getVertexPos(ver);if(i=-1)coutvv你要查找的頂點(diǎn)不存在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的頂點(diǎn)后做DFS遍歷后為:vvendl;DFS(G,0);templatevclassT,classEvoidGraphvT,E:ChangeGraph(GraphvT,E&G)inti,j,m;T*VerticesList=newTnumVertices;/頂點(diǎn)表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請輸入頂點(diǎn)總數(shù)和邊的總數(shù)!vvendl;cinnumvnume; for(i=0;iinputi;for(i=0;ivnumv;i+)insertVertex(inputi);for(j=0;jvnume;j+)coutvv請輸入要插入邊的兩個(gè)頂點(diǎn)和權(quán)值！vvendl;cinabc;insertEdge(a,b,c);deleteinput;/Queue.htemplatevclassTclassQueue/隊(duì)列抽象類protected:intrear,front;T*elements;intma

35、xSize;public:Queue()Queue(intsz);Queue()/隊(duì)尾與隊(duì)頭指針/隊(duì)列存放數(shù)組/隊(duì)列最大容量/構(gòu)造函數(shù)/析構(gòu)函數(shù)boolEnQueue(Tx);boolDeQueue(T&x);boolgetFront(T&x);boolIsEmpty()const/進(jìn)隊(duì)列/出隊(duì)列/取隊(duì)頭/判隊(duì)列空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ù)/判隊(duì)列滿elements=newTmaxSize;templateboolQueue:EnQueue(Tx)/入隊(duì)操作，若隊(duì)列不滿,則x入隊(duì),否則返回falseif(IsFull()=true)returnfalse;elementsrear=x;/先存入rear=(rear+1)%maxSize;/尾指針后移returntrue;templateboolQueuevT:DeQueue(T&x)出隊(duì)操作，若隊(duì)列不空則退隊(duì)頭元素并返回其值if(IsEmpty()=true)returnfalse;x=elementsfront;/先取隊(duì)頭front=(front+1

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

38、式lvvendl;coutsetw(60)|7.對圖G作查找頂點(diǎn)|endl;coutsetw(60)|8.退出程序|endl;coutsetw(60)|f;if(f=1)G.Input();if(f=2)G.HaveEdge(G);if(f=3)coutvv請輸入要開始搜索的頂點(diǎn)的下標(biāo)：vvendl;cinm;coutvvDFS搜索的結(jié)果為：;G.DFS(G,m);coutvvendl;if(f=4)coutvv請輸入要開始搜索的頂點(diǎn)的下標(biāo)：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)試與體會(huì)從一定程度上說，編一個(gè)程序并不難，難的是要把這個(gè)程序完全調(diào)試正確，但是不可能把程序的每一條執(zhí)行路徑都執(zhí)行一遍。也就是說，不可能保證我們的程序是百分之百的正確的。我們調(diào)試的目的是在程序沒有語法錯(cuò)誤的基礎(chǔ)上保證我們的程序能達(dá)到我們所需要的主要的功能。我們在調(diào)試前應(yīng)該要先明白我們要輸入些什么數(shù)據(jù)并且其應(yīng)該得到些什么樣的結(jié)果，這樣我們才能更早的查找出錯(cuò) 誤并成功調(diào)試出結(jié)果。4.2程序運(yùn)行結(jié)果|洼輔入F連蟆咋LIw碼！3請輸入要幵始搜索的頂點(diǎn)的下

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