圖的遍歷課程設(shè)計(jì)

1、<p><b>　　圖的遍歷</b></p><p><b>　　課 程 設(shè) 計(jì)</b></p><p><b>　　課程設(shè)計(jì)任務(wù)書(shū)</b></p><p>　　2010 ～2011 學(xué)年第1 學(xué)期</p><p>　　學(xué)生姓名： 專業(yè)班級(jí)：</p

2、><p>　　指導(dǎo)教師： 工作部門： </p><p><b>　　一、課程設(shè)計(jì)題目 </b></p><p><b>　　圖的遍歷</b></p><p>　　二、課程設(shè)計(jì)內(nèi)容（含技術(shù)指標(biāo)）</p><p>　　1．顯示圖的鄰接矩陣, 圖的鄰接表, 深

3、度優(yōu)先遍歷, 廣度優(yōu)先遍歷, 最小生成樹(shù)PRIM算法, 最小生成樹(shù)KRUSCAL算法,圖的連通分量。</p><p>　　2．當(dāng)用戶選擇的功能錯(cuò)誤時(shí)，系統(tǒng)會(huì)輸出相應(yīng)的提示。</p><p>　　3．通過(guò)圖操作的實(shí)現(xiàn)，把一些實(shí)際生活中的具體的事物抽象出來(lái)</p><p><b>　　三、進(jìn)度安排</b></p><p>　

4、　1．初步完成總體設(shè)計(jì)，搭好框架；</p><p>　　2．完成最低要求：兩種必須都要實(shí)現(xiàn)，寫出畫(huà)圖的思路；</p><p>　　3．進(jìn)一步要求：畫(huà)出圖的結(jié)構(gòu)，有興趣的同學(xué)可以進(jìn)一步改進(jìn)圖的效果。</p><p><b>　　四、基本要求</b></p><p>　　1．界面友好，函數(shù)功能要?jiǎng)澐趾?lt;/p>

5、<p>　　2．程序要加必要的注釋</p><p>　　3．要提供程序測(cè)試方案</p><p><b>　　目 錄</b></p><p>　　一 概述 .............................................1</p><p>　　1.問(wèn)題描述 ……………………………………

6、…………………………………………………..1</p><p>　　2.系統(tǒng)分析 ………………………………………………………………………………………..1</p><p>　　3.課程設(shè)計(jì)（論文）進(jìn)程安排 …………………………………………………………………..1</p><p>　　二.總體設(shè)計(jì)方案...................................

7、...2</p><p>　　1．整體設(shè)計(jì)思路...............................................................................................................................2</p><p>　　2．算法的整體思路 ………………………………………………………………

8、……………….3</p><p>　　3．工作內(nèi)容 ……………………………………………………………………………………….3</p><p>　　三 詳細(xì)設(shè)計(jì) ………………………………………………………4</p><p>　　1.詳細(xì)設(shè)計(jì)思路及算法 …………………………………………………………………………..4</p><p>　　2.程序流程

9、圖 ……………………………………………………………………………………11</p><p>　　四 程序的調(diào)試與運(yùn)行結(jié)果說(shuō)明……………………………… 12</p><p>　?。?運(yùn)行結(jié)果 ………………………………………………………………………………………12</p><p>　　五．課程設(shè)計(jì)總結(jié) ………………………………………………15</p><

10、;p>　　參考文獻(xiàn) …………………………………………………………16</p><p>　　附錄A 原程序清單 ………………………………………………16</p><p>　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)成績(jī)?cè)u(píng)定表 …………………………………30</p><p><b>　　一 概述</b></p><p><b>　　

11、1.問(wèn)題描述</b></p><p><b>　　函數(shù)功能要?jiǎng)澐趾?lt;/b></p><p><b>　　總體設(shè)計(jì)應(yīng)畫(huà)流程圖</b></p><p><b>　　程序要加必要的注釋</b></p><p><b>　　要提供程序測(cè)試方案</b>&

12、lt;/p><p><b>　　2.系統(tǒng)分析</b></p><p>　　掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計(jì)方法，具備初步的獨(dú)立分析和設(shè)計(jì)能力</p><p>　　初步掌握軟件開(kāi)發(fā)過(guò)程的問(wèn)題分析、系統(tǒng)設(shè)計(jì)、程序編碼、測(cè)試等基本方法和技能</p><p>　　提高綜合運(yùn)用所學(xué)的理論知識(shí)和方法獨(dú)立分析和解決問(wèn)題的能力</p>

13、<p>　　訓(xùn)練用系統(tǒng)的觀點(diǎn)和軟件開(kāi)發(fā)一般規(guī)范進(jìn)行軟件開(kāi)發(fā)，培養(yǎng)軟件工作者所應(yīng)具備的科學(xué)的工作方法和作風(fēng)</p><p>　　3.課程設(shè)計(jì)（論文）進(jìn)程安排</p><p><b>　　二.總體設(shè)計(jì)方案</b></p><p><b>　　1．整體設(shè)計(jì)思路</b></p><p><

14、b>　　圖的鄰接矩陣：</b></p><p>　　對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的圖，可以使用n*n的矩陣（二維數(shù)組）來(lái)表示它們間的鄰接關(guān)系。</p><p><b>　　圖的鄰接表：</b></p><p>　　鄰接表由表頭結(jié)點(diǎn)和表結(jié)點(diǎn)兩部分組成，其中圖中每個(gè)頂點(diǎn)均對(duì)應(yīng)一個(gè)存儲(chǔ)在數(shù)組中的表頭結(jié)點(diǎn)。如這個(gè)表頭結(jié)點(diǎn)所對(duì)應(yīng)的頂點(diǎn)存在相鄰頂

15、點(diǎn)，則把相鄰頂點(diǎn)依次存放于表頭結(jié)點(diǎn)所指向的單向鏈表中。</p><p>　　深度優(yōu)先遍歷的遞歸算法思想：</p><p>　　假定以圖中某個(gè)頂點(diǎn)Vi為出發(fā)點(diǎn)，首先訪問(wèn)出發(fā)點(diǎn)，然后選擇一個(gè)Vi的未訪問(wèn)過(guò)的鄰接點(diǎn)Vj，以Vj為新的出發(fā)點(diǎn)繼續(xù)進(jìn)行深度優(yōu)先搜索，直至圖中所有頂點(diǎn)都被訪問(wèn)過(guò)。</p><p>　　訪問(wèn)結(jié)點(diǎn)V并標(biāo)記結(jié)點(diǎn)V為已訪問(wèn)；</p><

16、p>　　查找結(jié)點(diǎn)V的第一個(gè)鄰接結(jié)點(diǎn)W；</p><p>　　若結(jié)點(diǎn)W的臨界結(jié)點(diǎn)W存在，則繼續(xù)執(zhí)行，否則算法結(jié)束；</p><p>　　若結(jié)點(diǎn)W尚未被訪問(wèn)，則遞歸訪問(wèn)結(jié)點(diǎn)W；</p><p>　　查找結(jié)點(diǎn)V的W臨界結(jié)點(diǎn)的下一個(gè)臨界結(jié)點(diǎn)W ，轉(zhuǎn)到步驟（3）。 </p><p><b>　　廣度優(yōu)先遍歷算法：</b>&l

17、t;/p><p>　　從圖的某一頂點(diǎn)Vi出發(fā)，訪問(wèn)此頂點(diǎn)后，依次訪問(wèn)Vi的各個(gè)未曾訪問(wèn)過(guò)的鄰接點(diǎn)，然后分別從這些鄰接點(diǎn)出發(fā)，直至圖中所有已有已被訪問(wèn)的頂點(diǎn)的鄰接點(diǎn)都被訪問(wèn)到。</p><p>　　訪問(wèn)初始結(jié)點(diǎn)V并標(biāo)記結(jié)點(diǎn)V為已訪問(wèn)；</p><p><b>　　結(jié)點(diǎn)V入隊(duì)列；</b></p><p>　　當(dāng)隊(duì)列非空時(shí)則繼續(xù)執(zhí)

18、行，否則算法結(jié)束；</p><p>　　出隊(duì)列取得隊(duì)頭結(jié)點(diǎn)U；</p><p>　　查找結(jié)點(diǎn)U的第一個(gè)鄰接結(jié)點(diǎn)W；</p><p>　　若結(jié)點(diǎn)U的鄰接結(jié)點(diǎn)W不存在，則轉(zhuǎn)到步驟（3），否則循環(huán)執(zhí)行下列步驟：</p><p>　?。?.1）若結(jié)點(diǎn)W尚未被訪問(wèn)，則訪問(wèn)結(jié)點(diǎn)W并標(biāo)記結(jié)點(diǎn)W為已訪問(wèn)；</p><p>　?。?.2

19、）結(jié)點(diǎn)W入隊(duì)；</p><p>　?。?.3）查找結(jié)點(diǎn)U的W鄰接結(jié)點(diǎn)的下一個(gè)鄰接結(jié)點(diǎn)W，轉(zhuǎn)到步驟（6）。</p><p><b>　　普利姆算法思想：</b></p><p>　　令集合U的初值為U={u0}，集合T的初值為T={}。從所有結(jié)點(diǎn)u屬于U和結(jié)點(diǎn)v屬于V\U的帶權(quán)邊中選出具有最小權(quán)值的邊（u，v），將結(jié)點(diǎn)v加入集合U中，將邊（u，v

20、）加入集合T中。如此不斷反復(fù)，當(dāng)U=V時(shí)，最小生成樹(shù)便構(gòu)造完畢。</p><p>　　克魯斯卡爾算法思想：</p><p>　　設(shè)無(wú)向連通帶權(quán)圖G=(V,E)，其中V為結(jié)點(diǎn)的集合，E為邊的集合。設(shè)帶權(quán)圖G的最小生成樹(shù)T由結(jié)點(diǎn)集合和邊的集合構(gòu)成，其初值為T=(v,{}),即初始時(shí)最小生成樹(shù)T只由帶權(quán)圖G中的結(jié)點(diǎn)集合組成，各結(jié)點(diǎn)之間沒(méi)有一條邊。這樣，最小生成樹(shù)T中的各個(gè)結(jié)點(diǎn)各自構(gòu)成一個(gè)連通分量

21、。然后，按照邊的權(quán)值遞增的順序考察帶權(quán)圖G中邊集合E的各條邊，若被考察的邊的兩個(gè)結(jié)點(diǎn)屬于T的兩個(gè)不同的連通分量，則將此邊加入懂啊最小生成樹(shù)T中，同時(shí)，把兩個(gè)連通分量連接為一個(gè)連通分量；若被考察的邊的兩個(gè)結(jié)點(diǎn)屬于T的同一個(gè)連通分量，則將此邊舍去。如此下去，當(dāng)T中的連通分量個(gè)數(shù)為1時(shí)，T中的該連通分量即為帶權(quán)圖G的一棵最小生成樹(shù)。</p><p><b>　　連通分量：</b></p>

22、;<p>　　非連通圖的每一個(gè)連通部分。</p><p><b>　　2．算法的整體思路</b></p><p>　　本系統(tǒng)能分別用鄰接矩陣存儲(chǔ)結(jié)構(gòu)和鄰接表存儲(chǔ)結(jié)構(gòu)構(gòu)造無(wú)向圖，然后在此無(wú)向圖中能實(shí)現(xiàn)深度優(yōu)先遍歷，廣度優(yōu)先遍歷，最小生成樹(shù)和連通分量的算法。</p><p><b>　　3．工作內(nèi)容</b><

23、;/p><p>　　1.顯示圖的鄰接矩陣, 圖的鄰接表, 深度優(yōu)先遍歷, 廣度優(yōu)先遍歷, 最小生成樹(shù)PRIM算法, 最小生成樹(shù)KRUSCAL算法,圖的連通分量。</p><p>　　2.當(dāng)用戶選擇的功能錯(cuò)誤時(shí)，系統(tǒng)會(huì)輸出相應(yīng)的提示。</p><p>　　3.通過(guò)圖操作的實(shí)現(xiàn)，把一些實(shí)際生活中的具體的事物抽象出來(lái)。</p><p><b>

24、;　　三 詳細(xì)設(shè)計(jì)</b></p><p>　　1.詳細(xì)設(shè)計(jì)思路及算法</p><p><b>　　圖1-1 無(wú)向圖</b></p><p>　　1.程序中所用變量的定義:</p><p>　　#include <iostream></p><p>　　#include &

25、lt;malloc.h></p><p>　　using namespace std; </p><p>　　#define int_max 10000</p><p>　　#define inf 9999 </p><p>　　#define max 20</p><p>　　2.鄰接矩陣的定義：</p&

26、gt;<p>　　typedef struct ArcCell</p><p><b>　　{</b></p><p><b>　　int adj;</b></p><p>　　char *info;</p><p>　　}ArcCell,AdjMatrix[20][20];</

27、p><p>　　typedef struct </p><p><b>　　{</b></p><p>　　char vexs[20];</p><p>　　AdjMatrix arcs;</p><p>　　int vexnum,arcnum;</p><p>　　}MGra

28、ph_L;</p><p>　　A 0 50 60 0 0 0 0</p><p>　　B 50 0 0 65 40 0 0</p><p>　　C 60 0 0 52 0 0 45</p><p>　　D 0 65 52 0 50 30 0</p><p&

29、gt;　　E 0 40 0 50 0 70 0</p><p>　　F 0 0 0 30 70 0 80</p><p>　　G 0 0 45 0 0 80 0</p><p><b>　　圖1-2 鄰接矩陣</b></p><p><b>　　3.鄰接表：&

30、lt;/b></p><p><b>　　表1-1 鄰接表</b></p><p><b>　　4.深度優(yōu)先遍歷：</b></p><p>　　void adjprint(algraph gra)</p><p><b>　　5.廣度優(yōu)先遍歷：</b></p>

31、<p>　　void bfstra(algraph gra)</p><p>　　6.最小生成樹(shù)PRIM算法：</p><p>　　7.最小生成樹(shù)KRUSCAL算法：</p><p><b>　　2.程序流程圖 </b></p><p>　　四 程序的調(diào)試與運(yùn)行結(jié)果說(shuō)明</p><p&g

32、t;<b>　　１.運(yùn)行結(jié)果</b></p><p>　　圖2-1 輸入頂點(diǎn)數(shù)</p><p><b>　　圖2-2 輸入權(quán)值</b></p><p><b>　　無(wú)向圖創(chuàng)建成功</b></p><p><b>　　圖2-3 菜單</b></p>

33、;<p><b>　　圖2-4 鄰接矩陣</b></p><p><b>　　圖2-5 鄰接表</b></p><p>　　圖2-6 深廣度優(yōu)先遍歷</p><p>　　圖2-7 最小生成樹(shù)</p><p><b>　　圖2-8 連通分量</b></p>

34、;<p><b>　　五．課程設(shè)計(jì)總結(jié)</b></p><p>　　課程設(shè)計(jì)是把我們所學(xué)的理論知識(shí)進(jìn)行系統(tǒng)的總結(jié)并應(yīng)用于實(shí)踐的良好機(jī)會(huì)，有利于加強(qiáng)我們用知識(shí)理論來(lái)分析實(shí)際問(wèn)題的能力，進(jìn)而加強(qiáng)了我們對(duì)知識(shí)認(rèn)識(shí)的實(shí)踐度，鞏固了我們的理論知識(shí)，深化了對(duì)知識(shí)的認(rèn)識(shí)，并為走向社會(huì)打下一個(gè)良好的基礎(chǔ)。</p><p>　　對(duì)于我們學(xué)生來(lái)講，此次課程設(shè)計(jì)是為了讓我們訓(xùn)

35、練自己的實(shí)際設(shè)計(jì)能力，通過(guò)設(shè)計(jì)實(shí)踐，去真正獲得此項(xiàng)目管理和團(tuán)隊(duì)協(xié)作等方面的基本訓(xùn)練和工作經(jīng)驗(yàn)。通過(guò)課程設(shè)計(jì)的一系列訓(xùn)練，我們能提高如何綜合運(yùn)用所學(xué)知識(shí)解決實(shí)際問(wèn)題的能力，以及獲得此項(xiàng)目管理和團(tuán)隊(duì)協(xié)作等等眾多方面的具體經(jīng)驗(yàn)，增強(qiáng)對(duì)相關(guān)課程具體內(nèi)容的理解和掌握能力，培養(yǎng)對(duì)整體課程知識(shí)綜合運(yùn)用和融會(huì)貫通能力。</p><p>　　通過(guò)這近一個(gè)星期的數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)實(shí)踐，我學(xué)到了很多東西。本次課程設(shè)計(jì)對(duì)我來(lái)說(shuō)正是一個(gè)提高

36、自己能力的機(jī)會(huì)，我好好的抓住機(jī)會(huì)，努力做好每一步，完善每一步。自己的C語(yǔ)言知識(shí)和數(shù)據(jù)結(jié)構(gòu)知識(shí)得到了鞏固，編程能力也有了一定的提高。同時(shí)也學(xué)會(huì)了解決問(wèn)題的方法。</p><p>　　此次課程設(shè)計(jì)也讓我認(rèn)識(shí)到必須培養(yǎng)嚴(yán)謹(jǐn)?shù)膽B(tài)度。自己在編程時(shí)經(jīng)常因?yàn)橐恍╊愃朴凇吧倭朔痔?hào)”的小錯(cuò)誤而導(dǎo)致錯(cuò)誤，不夠認(rèn)真細(xì)致，這給自己帶來(lái)了許多麻煩。編程是一件十分嚴(yán)謹(jǐn)?shù)氖虑椋莶坏民R虎。所以在今后自己一定要培養(yǎng)嚴(yán)謹(jǐn)?shù)膽B(tài)度。我想這不僅是對(duì)于程

37、序設(shè)計(jì)，做任何事都應(yīng)如此。</p><p>　　在實(shí)踐過(guò)程中，我和組員分工合作，勇于提出問(wèn)題，解決難題，在實(shí)踐中，我遇到了許多困難，但都一一克服了。最終我圓滿的完成此次課程設(shè)計(jì)，學(xué)到了很多東西。同時(shí)，程序還存在著一些缺陷，就是不能輸出原圖，存在一些局限性，不過(guò)我會(huì)繼續(xù)努力思考，完善程序，做到最好。</p><p>　　此次試驗(yàn)，老師對(duì)我的指導(dǎo)是至關(guān)重要的，在此我非常感謝老師，從她那我學(xué)到了

38、很多有關(guān)c語(yǔ)言的知識(shí)，為以后的學(xué)習(xí)打下了一定的基礎(chǔ)。</p><p>　　總的來(lái)說(shuō)，本次課程設(shè)計(jì)，不僅我的知識(shí)面有所提高，另外我的綜合素質(zhì)也有所提高，，比如說(shuō)：團(tuán)隊(duì)精神、提問(wèn)能力、思考能力等等。這次課程設(shè)計(jì)為我以后更好的學(xué)習(xí)和使用c語(yǔ)言打下了基礎(chǔ)。</p><p><b>　　參考文獻(xiàn)</b></p><p>　　[1]數(shù)據(jù)結(jié)構(gòu)—使用C語(yǔ)言（第

39、3版）朱戰(zhàn)立 編，西安交通大學(xué)出版社。</p><p>　　[2] Visual C++程序設(shè)計(jì)──基礎(chǔ)與實(shí)例分析.北京：清華大學(xué)出版社，2004</p><p><b>　　附錄A 原程序清單</b></p><p>　　#include <iostream></p><p>　　#include <

40、malloc.h></p><p>　　using namespace std; </p><p>　　#define int_max 10000</p><p>　　#define inf 9999 </p><p>　　#define max 20</p><p>　　//…………………………………………鄰接

41、矩陣定義……………………</p><p>　　typedef struct ArcCell</p><p><b>　　{</b></p><p><b>　　int adj;</b></p><p>　　char *info;</p><p>　　}ArcCell,AdjM

42、atrix[20][20];</p><p>　　typedef struct </p><p><b>　　{</b></p><p>　　char vexs[20];</p><p>　　AdjMatrix arcs;</p><p>　　int vexnum,arcnum;</p>

43、;<p>　　}MGraph_L;</p><p>　　//^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^</p><p>　　int localvex(MGraph_L G,char v)//返回V的位置</p><p><b>　　{</b></

44、p><p><b>　　int i=0;</b></p><p>　　while(G.vexs[i]!=v)</p><p><b>　　{</b></p><p><b>　　++i;</b></p><p><b>　　}</b>&

45、lt;/p><p><b>　　return i;</b></p><p><b>　　}</b></p><p>　　int creatMGraph_L(MGraph_L &G)//創(chuàng)建圖用鄰接矩陣表示</p><p><b>　　{</b></p><

46、;p>　　char v1,v2;</p><p>　　int i,j,w;</p><p>　　cout<<"…………創(chuàng)建無(wú)向圖…………"<<endl;<<"請(qǐng)輸入圖G頂點(diǎn)和弧的個(gè)數(shù):(4 6)不包括“()”"<<endl;</p><p>　　cin>>G.v

47、exnum>>G.arcnum;</p><p>　　for(i=0;i!=G.vexnum;++i)</p><p><b>　　{</b></p><p>　　cout<<"輸入頂點(diǎn)"<<i<<endl;</p><p>　　cin>>G

48、.vexs[i];</p><p><b>　　}</b></p><p>　　for(i=0;i!=G.vexnum;++i)</p><p>　　for(j=0;j!=G.vexnum;++j)</p><p><b>　　{ </b></p><p>　　G.arcs[

49、i][j].adj=int_max;</p><p>　　G.arcs[i][j].info=NULL;</p><p><b>　　}</b></p><p>　　for(int k=0;k!=G.arcnum;++k)</p><p><b>　　{ </b></p><p&

50、gt;　　cout<<"輸入一條邊依附的頂點(diǎn)和權(quán):(a b 3)不包括()"<<endl;</p><p>　　cin>>v1>>v2>>w;//輸入一條邊依附的兩點(diǎn)及權(quán)值</p><p>　　i=localvex(G,v1);//確定頂點(diǎn)V1和V2在圖中的位置</p><p>　　j=

51、localvex(G,v2);</p><p>　　G.arcs[i][j].adj=w;</p><p>　　G.arcs[j][i].adj=w;</p><p><b>　　}</b></p><p>　　cout<<"圖G鄰接矩陣創(chuàng)建成功！"<<endl;</p&

52、gt;<p>　　return G.vexnum;</p><p><b>　　}</b></p><p>　　void ljjzprint(MGraph_L G)</p><p><b>　　{</b></p><p><b>　　int i,j;</b><

53、;/p><p>　　for(i=0;i!=G.vexnum;++i)</p><p><b>　　{</b></p><p>　　for(j=0;j!=G.vexnum;++j)</p><p>　　cout<<G.arcs[i][j].adj<<" ";</p>&

54、lt;p>　　cout<<endl;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　int visited[max];//訪問(wèn)標(biāo)記</p><p><b>　　int we;</b></p>

55、<p>　　typedef struct arcnode//弧結(jié)點(diǎn)</p><p><b>　　{</b></p><p>　　int adjvex;//該弧指向的頂點(diǎn)的位置</p><p>　　struct arcnode *nextarc;//弧尾相同的下一條弧</p><p>　　char *info;/

56、/該弧信息</p><p><b>　　}arcnode;</b></p><p>　　typedef struct vnode//鄰接鏈表頂點(diǎn)頭接點(diǎn)</p><p><b>　　{</b></p><p>　　char data;//結(jié)點(diǎn)信息</p><p>　　arcno

57、de *firstarc;//指向第一條依附該結(jié)點(diǎn)的弧的指針</p><p>　　}vnode,adjlist;</p><p>　　typedef struct//圖的定義</p><p><b>　　{</b></p><p>　　adjlist vertices[max];</p><p>

58、　　int vexnum,arcnum;</p><p><b>　　int kind;</b></p><p><b>　　}algraph;</b></p><p>　　//…………………………………………隊(duì)列定義……………………</p><p>　　typedef struct qnode&l

59、t;/p><p><b>　　{</b></p><p><b>　　int data;</b></p><p>　　struct qnode *next;</p><p>　　}qnode,*queueptr;</p><p>　　typedef struct</p>

60、;<p><b>　　{</b></p><p>　　queueptr front;</p><p>　　queueptr rear;</p><p>　　}linkqueue;</p><p>　　//………………………………………………………………………</p><p>　　ty

61、pedef struct acr</p><p><b>　　{</b></p><p>　　int pre;//弧的一結(jié)點(diǎn)</p><p>　　int bak;//弧另一結(jié)點(diǎn)</p><p>　　int weight;//弧的權(quán)</p><p><b>　　}edg;</b>

62、;</p><p>　　int creatadj(algraph &gra,MGraph_L G)//用鄰接表存儲(chǔ)圖</p><p><b>　　{</b></p><p>　　int i=0,j=0;</p><p>　　arcnode *arc,*tem,*p;</p><p>　　f

63、or(i=0;i!=G.vexnum;++i)</p><p><b>　　{</b></p><p>　　gra.vertices[i].data=G.vexs[i];</p><p>　　gra.vertices[i].firstarc=NULL;</p><p><b>　　}</b><

64、/p><p>　　for(i=0;i!=G.vexnum;++i)</p><p><b>　　{</b></p><p>　　for(j=0;j!=G.vexnum;++j)</p><p><b>　　{</b></p><p>　　if(gra.vertices[i].fi

65、rstarc==NULL)</p><p><b>　　{</b></p><p>　　if(G.arcs[i][j].adj!=int_max&&j!=G.vexnum)</p><p><b>　　{</b></p><p>　　arc=(arcnode *)malloc(siz

66、eof(arcnode));</p><p>　　arc->adjvex=j;</p><p>　　gra.vertices[i].firstarc=arc;</p><p>　　arc->nextarc=NULL;</p><p><b>　　p=arc;</b></p><p>&

67、lt;b>　　++j;</b></p><p>　　while(G.arcs[i][j].adj!=int_max&&j!=G.vexnum)</p><p><b>　　{</b></p><p>　　tem=(arcnode *)malloc(sizeof(arcnode));</p><

68、;p>　　tem->adjvex=j; </p><p>　　gra.vertices[i].firstarc=tem;</p><p>　　tem->nextarc=arc;</p><p><b>　　arc=tem;</b></p><p><b>　　++j;</b>

69、</p><p><b>　　}</b></p><p><b>　　--j;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　else</b>

70、;</p><p><b>　　{</b></p><p>　　if(G.arcs[i][j].adj!=int_max&&j!=G.vexnum)</p><p><b>　　{</b></p><p>　　arc=(arcnode *)malloc(sizeof(arcnode)

71、);</p><p>　　arc->adjvex=j;</p><p>　　p->nextarc=arc;</p><p>　　arc->nextarc=NULL;</p><p><b>　　p=arc;</b></p><p><b>　　}</b>&l

72、t;/p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　gra.vexnum=G.vexnum;</p><p>　　gra.arcnum=G.arcnum;</p&

73、gt;<p>　　/*for(i=0;i!=gra.vexnum;++i)</p><p><b>　　{</b></p><p>　　arcnode *p;</p><p>　　cout<<i<<" ";</p><p>　　p=gra.vertices[i].

74、firstarc;</p><p>　　while(p!=NULL)</p><p><b>　　{</b></p><p>　　cout<<p->adjvex;</p><p>　　p=p->nextarc;</p><p><b>　　}</b>&

75、lt;/p><p>　　cout<<endl;</p><p><b>　　}*/</b></p><p>　　cout<<"圖G鄰接表創(chuàng)建成功！"<<endl;</p><p><b>　　return 1;</b></p><

76、;p><b>　　}</b></p><p>　　void adjprint(algraph gra)</p><p><b>　　{</b></p><p><b>　　int i;</b></p><p>　　for(i=0;i!=gra.vexnum;++i)<

77、;/p><p><b>　　{</b></p><p>　　arcnode *p;</p><p>　　cout<<i<<" ";</p><p>　　p=gra.vertices[i].firstarc;</p><p>　　while(p!=NULL)&

78、lt;/p><p><b>　　{</b></p><p>　　cout<<p->adjvex;</p><p>　　p=p->nextarc;</p><p><b>　　}</b></p><p>　　cout<<endl;</p&g

79、t;<p><b>　　}</b></p><p><b>　　}</b></p><p>　　int firstadjvex(algraph gra,vnode v)//返回依附頂點(diǎn)V的第一個(gè)點(diǎn)</p><p>　　//即以V為尾的第一個(gè)結(jié)點(diǎn)</p><p><b>　　{

80、</b></p><p>　　if(v.firstarc!=NULL)</p><p>　　return v.firstarc->adjvex;</p><p><b>　　}</b></p><p>　　int nextadjvex(algraph gra,vnode v,int w)//返回依附頂點(diǎn)

81、V的相對(duì)于W的下一個(gè)頂點(diǎn)</p><p><b>　　{</b></p><p>　　arcnode *p;</p><p>　　p=v.firstarc;</p><p>　　while(p!=NULL&&p->adjvex!=w)</p><p><b>　　{

82、</b></p><p>　　p=p->nextarc;</p><p><b>　　}</b></p><p>　　if(p->adjvex==w&&p->nextarc!=NULL)</p><p><b>　　{</b></p>&l

83、t;p>　　p=p->nextarc;</p><p>　　return p->adjvex;</p><p><b>　　}</b></p><p>　　if(p->adjvex==w&&p->nextarc==NULL)</p><p>　　return -10;<

84、/p><p><b>　　}</b></p><p>　　int initqueue(linkqueue &q)//初始化隊(duì)列</p><p><b>　　{</b></p><p>　　q.rear=(queueptr)malloc(sizeof(qnode));</p><

85、;p>　　q.front=q.rear;</p><p>　　if(!q.front)</p><p><b>　　return 0;</b></p><p>　　q.front->next=NULL;</p><p><b>　　return 1;</b></p><

86、;p><b>　　}</b></p><p>　　int enqueue(linkqueue &q,int e)//入隊(duì)</p><p><b>　　{</b></p><p>　　queueptr p;</p><p>　　p=(queueptr)malloc(sizeof(qnod

87、e));</p><p><b>　　if(!p)</b></p><p><b>　　return 0;</b></p><p>　　p->data=e;</p><p>　　p->next=NULL;</p><p>　　q.rear->next=p;&

88、lt;/p><p><b>　　q.rear=p;</b></p><p><b>　　return 1;</b></p><p><b>　　}</b></p><p>　　int dequeue(linkqueue &q,int &e)//出隊(duì)</p>

89、;<p><b>　　{</b></p><p>　　queueptr p;</p><p>　　if(q.front==q.rear)</p><p><b>　　return 0;</b></p><p>　　p=q.front->next;</p><p

90、>　　e=p->data;</p><p>　　q.front->next=p->next;</p><p>　　if(q.rear==p)</p><p>　　q.rear=q.front;</p><p><b>　　free(p);</b></p><p><b

91、>　　return 1;</b></p><p><b>　　}</b></p><p>　　int queueempty(linkqueue q)//判斷隊(duì)為空</p><p><b>　　{</b></p><p>　　if(q.front==q.rear)</p>

92、<p><b>　　return 1;</b></p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p>　　void bfstra(algraph gra)//廣度優(yōu)先遍歷</p><p><b>

93、　　{</b></p><p><b>　　int i,e;</b></p><p>　　linkqueue q;</p><p>　　for(i=0;i!=gra.vexnum;++i)</p><p>　　visited[i]=0;</p><p>　　initqueue(q);&

94、lt;/p><p>　　for(i=0;i!=gra.vexnum;++i)</p><p>　　if(!visited[i])</p><p>　　{ visited[i]=1;</p><p>　　cout<<gra.vertices[i].data;</p><p>　　enqueue(q,i);<

95、/p><p>　　while(!queueempty(q))</p><p><b>　　{</b></p><p>　　dequeue(q,e);</p><p>　　// cout<<" "<<e<<" ";</p><p&g

96、t;　　for(we=firstadjvex(gra,gra.vertices[e]);we>=0;we=nextadjvex(gra,gra.vertices[e],we))</p><p><b>　　{</b></p><p>　　if(!visited[we])</p><p><b>　　{</b><

97、/p><p>　　visited[we]=1;</p><p>　　cout<<gra.vertices[we].data;</p><p>　　enqueue(q,we);</p><p><b>　　}</b></p><p><b>　　}</b></p&

98、gt;<p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　int dfs(algraph gra,int i);//聲明DFS</p><p>　　int dfstra(algraph

99、 gra)</p><p><b>　　{</b></p><p><b>　　int i,j;</b></p><p>　　for(i=0;i!=gra.vexnum;++i)</p><p><b>　　{</b></p><p>　　visited

100、[i]=0;</p><p><b>　　}</b></p><p>　　for(j=0;j!=gra.vexnum;++j)</p><p><b>　　{</b></p><p>　　if(visited[j]==0)</p><p>　　dfs(gra,j);</

101、p><p><b>　　}</b></p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p>　　int dfs(algraph gra,int i)</p><p><b>　　{</b

102、></p><p>　　visited[i]=1;</p><p><b>　　int we1;</b></p><p>　　// cout<<i<<visited[i]<<endl;</p><p>　　cout<<gra.vertices[i].data;<

103、/p><p>　　// cout<<endl;</p><p>　　for(we=firstadjvex(gra,gra.vertices[i]);we>=0;we=nextadjvex(gra,gra.vertices[i],we))</p><p><b>　　{</b></p><p>　　// co

104、ut<<we<<visited[we]<<endl;</p><p><b>　　we1=we;</b></p><p>　　// cout<<nextadjvex(gra,gra.vertices[i],we)<<endl;</p><p>　　if(visited[we]==0)&

105、lt;/p><p>　　// cout<<</p><p>　　dfs(gra,we);//<<endl;</p><p>　　// cout<<i<<we1<<endl;</p><p><b>　　we=we1;</b></p><p>

106、;　　// cout<<nextadjvex(gra,gra.vertices[i],we)<<endl; </p><p><b>　　}</b></p><p>　　return 12;</p><p><b>　　}</b></p><p>　　int bfstra_

107、fen(algraph gra)//求連通分量</p><p><b>　　{</b></p><p><b>　　int i,j;</b></p><p>　　for(i=0;i!=gra.vexnum;++i)</p><p><b>　　{</b></p>

108、<p>　　visited[i]=0;</p><p><b>　　}</b></p><p>　　for(j=0;j!=gra.vexnum;++j)</p><p><b>　　{</b></p><p>　　if(visited[j]==0)</p><p>

109、<b>　　{</b></p><p>　　dfs(gra,j);</p><p>　　cout<<endl;</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　return

110、 0;</b></p><p><b>　　}</b></p><p>　　typedef struct </p><p><b>　　{</b></p><p>　　int adjvex;</p><p>　　int lowcost;</p>&l

111、t;p>　　}closedge;</p><p>　　/*int minimum(closedge *p);</p><p>　　int minispantree(MGraph_L G,char u)</p><p><b>　　{</b></p><p>　　int k,j,i;</p><p

112、>　　closedge closedge_a[20];</p><p>　　k=localvex(G,u);</p><p>　　// cout<<k<<endl;</p><p>　　for(j=0;j!=G.vexnum;++j)</p><p><b>　　{</b></p>

113、;<p><b>　　if(j!=k)</b></p><p><b>　　{ </b></p><p>　　closedge_a[j].adjvex=u;</p><p>　　closedge_a[j].lowcost=G.arcs[k][j].adj;</p><p><b&

114、gt;　　}</b></p><p>　　for(i=1;i!=G.vexnum;++i)</p><p><b>　　{</b></p><p>　　k=minimum(closedge_a);</p><p><b>　　cout<<k;</b></p>&

115、lt;p>　　cout<<closedge_a[k].adjvex<<" "<<G.vexs[k]<<endl;</p><p>　　closedge_a[k].lowcost=0;</p><p>　　for(j=0;j!=G.vexnum;++j)</p><p>　　if(G.arcs[

116、k][j].adj<closedge_a[j].lowcost)</p><p><b>　　{ </b></p><p>　　closedge_a[j].adjvex=G.vexs[k];</p><p>　　closedge_a[j].lowcost=G.arcs[k][j].adj;</p><p><

117、b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p>　

118、　int minimum(closedge *p)</p><p><b>　　{</b></p><p>　　int s=10000;</p><p>　　for(;p!=NULL;++p)</p><p><b>　　{</b></p><p>　　if(s>p-&

119、gt;lowcost)</p><p>　　s=p->lowcost;</p><p><b>　　}</b></p><p><b>　　return s;</b></p><p><b>　　}*/</b></p><p>　　int prim

120、(int g[][max],int n) //最小生成樹(shù)PRIM算法</p><p><b>　　{</b></p><p>　　int lowcost[max],prevex[max]; //LOWCOST[]存儲(chǔ)當(dāng)前集合U分別到剩余結(jié)點(diǎn)的最短路徑</p><p>　　//prevex[]存儲(chǔ)最短路徑在U中的結(jié)點(diǎn)</p><

121、;p>　　int i,j,k,min; </p><p>　　for(i=2;i<=n;i++) //n個(gè)頂點(diǎn)，n-1條邊 </p><p><b>　　{</b></p><p>　　lowcost[i]=g[1][i]; //初始化 </p><p>　　prevex[i]=1; //頂點(diǎn)未加入到最小生成

122、樹(shù)中 </p><p><b>　　} </b></p><p>　　lowcost[1]=0; //標(biāo)志頂點(diǎn)1加入U(xiǎn)集合 </p><p>　　for(i=2;i<=n;i++) //形成n-1條邊的生成樹(shù) </p><p><b>　　{</b></p><p>&

123、lt;b>　　min=inf; </b></p><p><b>　　k=0; </b></p><p>　　for(j=2;j<=n;j++) //尋找滿足邊的一個(gè)頂點(diǎn)在U,另一個(gè)頂點(diǎn)在V的最小邊 </p><p>　　if((lowcost[j]<min)&&(lowcost[j]!=0)) &

124、lt;/p><p><b>　　{</b></p><p>　　min=lowcost[j]; </p><p><b>　　k=j; </b></p><p><b>　　} </b></p><p>　　printf("(%d,%d)%d\t&

125、quot;,prevex[k]-1,k-1,min); </p><p>　　lowcost[k]=0; //頂點(diǎn)k加入U(xiǎn) </p><p>　　for(j=2;j<=n;j++) //修改由頂點(diǎn)k到其他頂點(diǎn)邊的權(quán)值 </p><p>　　if(g[k][j]<lowcost[j]) </p><p><b>　　{&l

126、t;/b></p><p>　　lowcost[j]=g[k][j]; </p><p>　　prevex[j]=k; </p><p><b>　　} </b></p><p>　　printf("\n"); </p><p><b>　　} </b&

127、gt;</p><p><b>　　return 0;</b></p><p><b>　　} </b></p><p>　　int acrvisited[100];//kruscal弧標(biāo)記數(shù)組</p><p>　　int find(int acrvisited[],int f)</p>

128、<p><b>　　{</b></p><p>　　while(acrvisited[f]>0)</p><p>　　f=acrvisited[f];</p><p><b>　　return f;</b></p><p><b>　　}</b></p

129、><p>　　void kruscal_arc(MGraph_L G,algraph gra)</p><p><b>　　{ </b></p><p>　　edg edgs[20];</p><p>　　int i,j,k=0;</p><p>　　for(i=0;i!=G.vexnum;++i)&

130、lt;/p><p>　　for(j=i;j!=G.vexnum;++j)</p><p><b>　　{</b></p><p>　　if(G.arcs[i][j].adj!=10000)</p><p><b>　　{</b></p><p>　　edgs[k].pre=i;&

131、lt;/p><p>　　edgs[k].bak=j;</p><p>　　edgs[k].weight=G.arcs[i][j].adj;</p><p><b>　　++k;</b></p><p><b>　　}</b></p><p><b>　　}</b&

132、gt;</p><p>　　int x,y,m,n;</p><p>　　int buf,edf;</p><p>　　for(i=0;i!=gra.arcnum;++i)</p><p>　　acrvisited[i]=0; </p><p>　　for(j=0;j!=G.arcnum;++j)</p>

133、<p><b>　　{</b></p><p><b>　　m=10000;</b></p><p>　　for(i=0;i!=G.arcnum;++i)</p><p><b>　　{</b></p><p>　　if(edgs[i].weight<m)&l

134、t;/p><p><b>　　{</b></p><p>　　m=edgs[i].weight;</p><p>　　x=edgs[i].pre;</p><p>　　y=edgs[i].bak;</p><p><b>　　n=i;</b></p><p&g

135、t;<b>　　}</b></p><p><b>　　}</b></p><p>　　// cout<<x<<y<<m;</p><p>　　// cout<<endl;</p><p>　　buf=find(acrvisited,x);<

136、/p><p>　　edf=find(acrvisited,y); </p><p>　　// cout<<buf<<" "<<edf<<endl;</p><p>　　edgs[n].weight=10000;</p><p>　　if(buf!=edf)</p>

137、<p><b>　　{</b></p><p>　　acrvisited[buf]=edf;</p><p>　　cout<<"("<<x<<","<<y<<")"<<m;</p><p>　　cou

138、t<<endl;</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void main()</p><p><b>　　{ </b>

139、;</p><p>　　algraph gra;</p><p>　　MGraph_L G;</p><p>　　int i,d,g[20][20];</p><p>　　char a='a';</p><p>　　d=creatMGraph_L(G);</p><p>　　cr

140、eatadj(gra,G);</p><p><b>　　vnode v;</b></p><p>　　cout<<endl<<"……####注意：若該圖為非強(qiáng)連通圖(含有多個(gè)連通分量)時(shí)"<<endl</p><p>　　<<" 最小生成樹(shù)不存在,則顯示為

141、非法值。"<<endl<<endl;</p><p>　　cout<<"…………………菜單……………………"<<endl<<endl;</p><p>　　cout<<"0、顯示該圖的鄰接矩陣……………………"<<endl;</p><p

142、>　　cout<<"1、顯示該圖的鄰接表……………………"<<endl;</p><p>　　cout<<"2、深度優(yōu)先遍歷…………………………"<<endl;</p><p>　　cout<<"3、廣度優(yōu)先遍歷…………………………"<<endl;<

143、;/p><p>　　cout<<"4、最小生成樹(shù)PRIM算法…………………"<<endl;</p><p>　　cout<<"5、最小生成樹(shù)KRUSCAL算法………………"<<endl;</p><p>　　cout<<"6、該圖的連通分量………………………&q

144、uot;<<endl<<endl;</p><p><b>　　int s;</b></p><p>　　char y='y';</p><p>　　while(y='y')</p><p><b>　　{</b></p><

145、;p>　　cout<<"請(qǐng)選擇菜單："<<endl;</p><p><b>　　cin>>s;</b></p><p><b>　　switch(s)</b></p><p><b>　　{</b></p><p>

146、;<b>　　case 0:</b></p><p>　　cout<<"鄰接矩陣顯示如下："<<endl;</p><p>　　ljjzprint(G);</p><p><b>　　break;</b></p><p><b>　　case 1

147、:</b></p><p>　　cout<<"鄰接表顯示如下："<<endl;</p><p>　　adjprint(gra);</p><p><b>　　break;</b></p><p><b>　　case 2:</b></p&