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

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

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

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

文檔簡介

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

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

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

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

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

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

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

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

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

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

11、1.問題描述　　函數(shù)功能要劃分好　　總體設(shè)計應畫流程圖　　程序要加必要的注釋　　要提供程序測試方案&

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

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

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

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

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

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

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

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

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

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

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

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

24、;　　三詳細設(shè)計　　1.詳細設(shè)計思路及算法　　圖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)試與運行結(jié)果說明<p&g

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

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

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

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

36、自己能力的機會，我好好的抓住機會，努力做好每一步，完善每一步。自己的C語言知識和數(shù)據(jù)結(jié)構(gòu)知識得到了鞏固，編程能力也有了一定的提高。同時也學會了解決問題的方法。　　此次課程設(shè)計也讓我認識到必須培養(yǎng)嚴謹?shù)膽B(tài)度。自己在編程時經(jīng)常因為一些類似于“少了分號”的小錯誤而導致錯誤，不夠認真細致，這給自己帶來了許多麻煩。編程是一件十分嚴謹?shù)氖虑椋莶坏民R虎。所以在今后自己一定要培養(yǎng)嚴謹?shù)膽B(tài)度。我想這不僅是對于程

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

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

39、3版）朱戰(zhàn)立編，西安交通大學出版社。　　[2] Visual C++程序設(shè)計──基礎(chǔ)與實例分析.北京：清華大學出版社，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;<<"請輸入圖G頂點和弧的個數(shù):(4 6)不包括“()”"<<endl;　　cin>>G.v

47、exnum>>G.arcnum;　　for(i=0;i!=G.vexnum;++i)　　{　　cout<<"輸入頂點"<<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<<"輸入一條邊依附的頂點和權(quán):(a b 3)不包括()"<<endl;　　cin>>v1>>v2>>w;//輸入一條邊依附的兩點及權(quán)值　　i=localvex(G,v1);//確定頂點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];//訪問標記　　int we;

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

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

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

58、　　int vexnum,arcnum;　　int kind;　　}algraph;　　//…………………………………………隊列定義……………………　　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é)點　　int bak;//弧另一結(jié)點　　int weight;//弧的權(quán)　　}edg;

62、;　　int creatadj(algraph &gra,MGraph_L G)//用鄰接表存儲圖　　{　　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)//返回依附頂點V的第一個點　　//即以V為尾的第一個結(jié)點　　{

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

81、V的相對于W的下一個頂點　　{　　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)//初始化隊列　　{　　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)//入隊　　{　　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)//出隊

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)//判斷隊為空　　{　　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[]存儲當前集合U分別到剩余結(jié)點的最短路徑　　//prevex[]存儲最短路徑在U中的結(jié)點<

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

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

123、lt;b>　　min=inf; 　　k=0; 　　for(j=2;j<=n;j++) //尋找滿足邊的一個頂點在U,另一個頂點在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; //頂點k加入U 　　for(j=2;j<=n;j++) //修改由頂點k到其他頂點邊的權(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弧標記數(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<<"……####注意：若該圖為非強連通圖(含有多個連通分量)時"<<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<<"請選擇菜單："<<endl;　　cin>>s;　　switch(s)　　{

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

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

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

溫馨提示

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

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

文檔簡介

溫馨提示

最新文檔

評論

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

文檔簡介

溫馨提示

最新文檔

評論

免費下載