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

上傳人：奔*** IP屬地：河北更新時(shí)間：2024-03-25 格式：doc 頁(yè)數(shù)：34 大?。?57.00KB 人氣指數(shù)：12 舉報(bào) 版權(quán)申訴

2023年全國(guó)碩士研究生考試考研英語(yǔ)一試題真題（含答案詳解+作文范文）_第1頁(yè)

已閱讀1頁(yè)，還剩33頁(yè)未讀，繼續(xù)免費(fèi)閱讀

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

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

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

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

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

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

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

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

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

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

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

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

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

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

14、b>　　圖的鄰接矩陣：　　對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的圖，可以使用n*n的矩陣（二維數(shù)組）來表示它們間的鄰接關(guān)系。　　圖的鄰接表：　　鄰接表由表頭結(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)所指向的單向鏈表中。　　深度優(yōu)先遍歷的遞歸算法思想：　　假定以圖中某個(gè)頂點(diǎn)Vi為出發(fā)點(diǎn)，首先訪問出發(fā)點(diǎn)，然后選擇一個(gè)Vi的未訪問過的鄰接點(diǎn)Vj，以Vj為新的出發(fā)點(diǎn)繼續(xù)進(jìn)行深度優(yōu)先搜索，直至圖中所有頂點(diǎn)都被訪問過。　　訪問結(jié)點(diǎn)V并標(biāo)記結(jié)點(diǎn)V為已訪問；<

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

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

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

19、）結(jié)點(diǎn)W入隊(duì)；　?。?.3）查找結(jié)點(diǎn)U的W鄰接結(jié)點(diǎn)的下一個(gè)鄰接結(jié)點(diǎn)W，轉(zhuǎn)到步驟（6）。　　普利姆算法思想：　　令集合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í)，最小生成樹便構(gòu)造完畢。　　克魯斯卡爾算法思想：　　設(shè)無向連通帶權(quán)圖G=(V,E)，其中V為結(jié)點(diǎn)的集合，E為邊的集合。設(shè)帶權(quán)圖G的最小生成樹T由結(jié)點(diǎn)集合和邊的集合構(gòu)成，其初值為T=(v,{}),即初始時(shí)最小生成樹T只由帶權(quán)圖G中的結(jié)點(diǎn)集合組成，各結(jié)點(diǎn)之間沒有一條邊。這樣，最小生成樹T中的各個(gè)結(jié)點(diǎn)各自構(gòu)成一個(gè)連通分量

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

36、自己能力的機(jī)會(huì)，我好好的抓住機(jī)會(huì)，努力做好每一步，完善每一步。自己的C語(yǔ)言知識(shí)和數(shù)據(jù)結(jié)構(gòu)知識(shí)得到了鞏固，編程能力也有了一定的提高。同時(shí)也學(xué)會(huì)了解決問題的方法。　　此次課程設(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ì)致，這給自己帶來了許多麻煩。編程是一件十分嚴(yán)謹(jǐn)?shù)氖虑椋莶坏民R虎。所以在今后自己一定要培養(yǎng)嚴(yán)謹(jǐn)?shù)膽B(tài)度。我想這不僅是對(duì)于程

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

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

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

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

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

42、atrix[20][20];　　typedef struct 　　{　　char vexs[20];　　AdjMatrix arcs;　　int vexnum,arcnum;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

60、;　　{　　queueptr front;　　queueptr rear;　　}linkqueue;　　//………………………………………………………………………　　ty

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

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

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

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

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

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

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

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

69、　　}　　--j;　　}　　}　　else

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

99、 gra)　　{　　int i,j;　　for(i=0;i!=gra.vexnum;++i)　　{　　visited

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

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

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

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

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

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

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

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

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

109、　　{　　dfs(gra,j);　　cout<<endl;　　}　　}　　return

110、 0;　　}　　typedef struct 　　{　　int adjvex;　　int lowcost;&l

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

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

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

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

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

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

117、b>　　}　　}　　}　　return 0;　　}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

138、t<<endl;　　}　　}　　}　　void main()　　{

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

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

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

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

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

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

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

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

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

眾賞文庫(kù)> 全部分類> 畢業(yè)設(shè)計(jì)

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫(kù)僅提供信息存儲(chǔ)空間，僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理，對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請(qǐng)與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

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

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

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

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

免費(fèi)下載