景區(qū)旅游信息管理系統(tǒng)_第1頁(yè)
景區(qū)旅游信息管理系統(tǒng)_第2頁(yè)
景區(qū)旅游信息管理系統(tǒng)_第3頁(yè)
景區(qū)旅游信息管理系統(tǒng)_第4頁(yè)
景區(qū)旅游信息管理系統(tǒng)_第5頁(yè)
已閱讀5頁(yè),還剩25頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

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

文檔簡(jiǎn)介

1、校園旅游信息管理系統(tǒng)1.1 項(xiàng)目需求分析在旅游景區(qū), 經(jīng)常會(huì)遇到游客打聽(tīng)從一個(gè)景點(diǎn)到另一個(gè)景點(diǎn)的最短路徑和最短距離,這類游客不喜歡按照導(dǎo)游圖的線路來(lái)游覽,而是挑選自己感興趣的景點(diǎn)游覽。為于幫助這類游客信息查詢, 就需要計(jì)算出所有景點(diǎn)之間最短路徑和最短距離。算法采用迪杰斯特拉算法或弗洛伊德算法均可。建立一個(gè)景區(qū)旅游信息管理系統(tǒng),實(shí)現(xiàn)的主要功能包括制訂旅游景點(diǎn)導(dǎo)游線路策略和制訂景區(qū)道路鋪設(shè)策略。任務(wù)中景點(diǎn)分布是一個(gè)無(wú)向帶權(quán)連通圖,圖中邊的權(quán)值是景點(diǎn)之間的距離。1)景區(qū)旅游信息管理系統(tǒng)中制訂旅游景點(diǎn)導(dǎo)游線路策略,首先通過(guò)遍歷景點(diǎn),給出一個(gè)入口景點(diǎn),建立一個(gè)導(dǎo)游線路圖,導(dǎo)游線路圖用有向圖表示。遍歷采用

2、深度優(yōu)先策略,這也比較符合游客心理。( 2)為了使導(dǎo)游線路圖能夠優(yōu)化,可通過(guò)拓樸排序判斷圖中有無(wú)回路,若有回路,則打印輸出回路中的景點(diǎn),供人工優(yōu)化。( 3)在導(dǎo)游線路圖中,還為一些不愿按線路走的游客提供信息服務(wù),比如從一個(gè)景點(diǎn)到另一個(gè)景點(diǎn)的最短路徑和最短距離。 在本線路圖中將輸出任意景點(diǎn)間的最短路徑和最短距離。( 4)在景區(qū)建設(shè)中,道路建設(shè)是其中一個(gè)重要內(nèi)容。道路建設(shè)首先要保證能連通所有景點(diǎn), 但又要花最小的代價(jià),可以通過(guò)求最小生成樹(shù)來(lái)解決這個(gè)問(wèn)題。本任務(wù)中假設(shè)修建道路的代價(jià)只與它的里程相關(guān)。因此歸納起來(lái),本任務(wù)有如下功能模塊:創(chuàng)建景區(qū)景點(diǎn)分布圖;輸出景區(qū)景點(diǎn)分布圖(鄰接矩陣)輸出導(dǎo)游線路圖;

3、判斷導(dǎo)游線路圖有無(wú)回路;求兩個(gè)景點(diǎn)間的最短路徑和最短距離;輸出道路修建規(guī)劃圖。主程序用菜單選項(xiàng)供用戶選擇功能模塊。1.2 項(xiàng)目設(shè)計(jì)流程1.2.1項(xiàng)目總體框架校園旅游信息管理系統(tǒng)創(chuàng)輸輸導(dǎo)兩輸建出出游個(gè)出景景景線景道區(qū)區(qū)區(qū)路點(diǎn)路景景導(dǎo)圖間修點(diǎn)點(diǎn)游有的建分分線無(wú)最規(guī)布布路回短劃圖圖圖路路圖1.2.2項(xiàng)目數(shù)據(jù)結(jié)構(gòu)#ifndef SUCCESS/ 標(biāo)志位成功#define SUCCESS1#endif#ifndef FAILURE/ 標(biāo)志位失敗#define FAILURE0#endif#ifndef INF/ 標(biāo)志位無(wú)窮#define INF0x3f3fffff#endif#ifndef MAXNUM

4、#define MAXNUM20#endiftypedef bool STATUS;/ 定義函數(shù)狀態(tài)數(shù)據(jù)類型typedef char VERTEXTYPEMAXNUM11;/ 定義頂點(diǎn)向量數(shù)據(jù)類型typedef int ADJMATRIXMAXNUMMAXNUM;/ 定義鄰接矩陣數(shù)據(jù)類型typedef struct GRAPH/ 定義圖數(shù)據(jù)類型VERTEXTYPE Vexs;/ 圖的頂點(diǎn)向量ADJMATRIX Arcs;/ 圖的鄰接矩陣int VexNum;/ 圖的當(dāng)前頂點(diǎn)int ArcNum;/ 圖的當(dāng)前弧*PGRAPH;/ 定義圖的指針數(shù)據(jù)類型typedef struct CLOSEDGE

5、/ 定義輔助數(shù)組數(shù)據(jù)類型VERTEXTYPE Vexs;/ 圖的頂點(diǎn)向量int LowcostMAXNUM;/*PCLOSEDGE;/ 定義輔助數(shù)組指針數(shù)據(jù)類型1.2.3項(xiàng)目模塊設(shè)計(jì)創(chuàng)建景區(qū)景點(diǎn)分布圖一. 鄰接矩陣(Adjacency Matrix)(二維數(shù)組表示法)在圖的鄰接矩陣表示中,有一個(gè)記錄各個(gè)頂點(diǎn)信息的頂點(diǎn)表,還有一個(gè)表示各個(gè)頂點(diǎn)之間關(guān)系的鄰接矩陣。設(shè)圖 A = (V, E)是一個(gè)有n個(gè)頂點(diǎn)的圖 ,圖的鄰接矩陣是一個(gè)二維數(shù)組A.edgenn定義 ( 滿足如下條件的n 階矩陣 ) :,A.Edgei j1, if ( Eor (i, j)E )0,otherwise無(wú)向圖數(shù)組表示法特點(diǎn)

6、:1)無(wú)向圖鄰接矩陣是對(duì)稱矩陣,同一條邊表示了兩次;2)頂點(diǎn) v 的度:在無(wú)向圖中等于二維數(shù)組對(duì)應(yīng)行(或列)中1 的個(gè)數(shù);在有向圖中, 統(tǒng)計(jì)第 i 行 1 的個(gè)數(shù)可得頂點(diǎn) i的出度,統(tǒng)計(jì)第 j 列 1的個(gè)數(shù)可得頂點(diǎn) j 的入度。3)判斷兩頂點(diǎn) v、 u 是否為鄰接點(diǎn):只需判二維數(shù)組對(duì)應(yīng)分量是否為1;4)頂點(diǎn)不變,在圖中增加、刪除邊:只需對(duì)二維數(shù)組對(duì)應(yīng)分量賦值1 或清 0;5)設(shè)存儲(chǔ)頂點(diǎn)的一維數(shù)組大小為n( 圖的頂點(diǎn)數(shù) n), G 占用存儲(chǔ)空間: n+n2; G 占用存儲(chǔ)空間只與它的頂點(diǎn)數(shù)有關(guān),與邊數(shù)無(wú)關(guān);適用于邊稠密的圖;流程圖:初始化圖的頂點(diǎn)數(shù)scanf(%d,&pGraph-VexNum)

7、;if(pGraph-VexNum20)初始化圖的弧數(shù)scanf(%d,&pGraph-ArcNum);if(pGraph-ArcNum20)初始化圖的頂點(diǎn)名稱初始化圖的弧權(quán)值為最大值輸入弧的信息終止程序:/ 創(chuàng)建景區(qū)景點(diǎn)分布圖STATUS CreateGraph(PGRAPH pGraph)printf(ttt_n);printf(nttt$t創(chuàng)建景區(qū)景點(diǎn)分布圖t$n);printf(ttt_n);/ 初始化圖的頂點(diǎn)數(shù)printf(ttt初始化頂點(diǎn)數(shù)和弧度數(shù).n);printf(ttt請(qǐng)輸入圖的頂點(diǎn)數(shù)(VexNum);/ 檢查if(pGraph-VexNum20)printf(ttt警告:輸

8、入數(shù)據(jù)錯(cuò)誤! ! n);printf(ttt按任意鍵回主菜單! ! );getch();return FAILURE;/ 初始化圖的弧數(shù)printf(ttt請(qǐng)輸入圖的弧度數(shù)(ArcNum);/ 檢查if(pGraph-ArcNum20)printf(ttt警告:輸入數(shù)據(jù)錯(cuò)誤! ! n);printf(ttt按任意鍵回主菜單! ! );getch();return FAILURE;/ 初始化圖的頂點(diǎn)名稱printf(ttt-n);printf(ttt初始化的頂點(diǎn)名稱.n);for(int i=0;iVexNum;i+)printf(ttt請(qǐng)輸入第 %d個(gè)頂點(diǎn)名稱: ,i+1);scanf(%s,

9、pGraph-Vexsi);/ 初始化圖的弧權(quán)值為最大值for(i=0;iVexNum;i+)for(int j=0;jVexNum;j+)pGraph-Arcsij=INF;/ 輸入弧的信息printf(ttt-n);printf(ttt初始化的弧的信息.n);printf(ttt請(qǐng)輸入弧的信息( 注:從 0 開(kāi)始 ) : n);for(i=0;iArcNum;i+)int Stav,Endv,Weight;printf(ttt請(qǐng)輸入第 %d條弧 ( 格式: Vi Vj Weight): ,i+1);scanf(%d%d%d,&Stav,&Endv,&Weight);pGraph-ArcsE

10、ndvStav=Weight;pGraph-ArcsStavEndv=Weight;printf(ttt創(chuàng)建景區(qū)景點(diǎn)分布圖成功! n);printf(ttt按任意鍵回主菜單! ! );getch();return SUCCESS;輸出景區(qū)景點(diǎn)分布圖流程圖:景區(qū)景點(diǎn)名稱i=0iVexNumt,pGraph-Vexsi);景區(qū)景點(diǎn)信息i=0iVexNumj=0jVexNumi+終止if(pGraph-Arcsij=t,pGraph-j+INF)Arcsij);printf(t);程序:/ 輸出景區(qū)景點(diǎn)分布圖STATUS PrintGraph(const PGRAPH pGraph)printf(t

11、tt_n);printf(nttt$t顯示景區(qū)景點(diǎn)分布圖t$n);printf(ttt_nn);/printf(t景區(qū)景點(diǎn)名稱 .nt);for(int i=0;iVexNum;i+)printf(%st,pGraph-Vexsi);printf(nnt景區(qū)景點(diǎn)信息.n);for(i=0;iVexNum;i+)printf(t_nt);for(int j=0;jVexNum;j+)if(pGraph-Arcsij=INF)printf( t);elseprintf(%dt,pGraph-Arcsij);printf(n);printf(t_nt);printf(按任意鍵回主菜單! ! );ge

12、tch();return SUCCESS;輸出景區(qū)導(dǎo)游線路圖圖的遍歷從圖中某一頂點(diǎn)出發(fā)訪遍圖中所有的頂點(diǎn),且使每個(gè)頂點(diǎn)僅被訪問(wèn)一次,這一過(guò)程就叫做圖的遍歷 (Traversing Graph)。圖中可能存在回路,且圖的任一頂點(diǎn)都可能與其它頂點(diǎn)相通,在訪問(wèn)完某個(gè)頂點(diǎn)之后可能會(huì)沿著某些邊又回到了曾經(jīng)訪問(wèn)過(guò)的頂點(diǎn)。為了避免重復(fù)訪問(wèn),可設(shè)置一個(gè)標(biāo)志頂點(diǎn)是否被訪問(wèn)過(guò)的輔助數(shù)組visited 。輔助數(shù)組visited 的初始狀態(tài)為0,在圖的遍歷過(guò)程中,一旦某一個(gè)頂點(diǎn)i被訪問(wèn)就立即讓visited i為 1,防止它被多次訪問(wèn)。兩種圖的遍歷方法:深度優(yōu)先搜索,DFS (Depth First Search)廣

13、度優(yōu)先搜索BFS (Breadth First Search)廣度優(yōu)先搜索遍歷圖(BFS)對(duì)連通圖,從起始點(diǎn)V 到其余各頂點(diǎn)必定存在路徑。其中, V-w1, V-w 2, V-w 8 的路徑長(zhǎng)度為1;V-w7, V-w 3, V-w 5 的路徑長(zhǎng)度為2;V-w6, V-w 4 的路徑長(zhǎng)度為3從圖中的某個(gè)頂點(diǎn)V0 出發(fā),并在訪問(wèn)此頂點(diǎn)之后依次訪問(wèn)V0 的所有未被訪問(wèn)過(guò)的鄰接點(diǎn),之后按這些頂點(diǎn)被訪問(wèn)的先后次序依次訪問(wèn)它們的鄰接點(diǎn),直至圖中所有和V0 有路徑相通的頂點(diǎn)都被訪問(wèn)到。若此時(shí)圖中尚有頂點(diǎn)未被訪問(wèn), 則另選圖中一個(gè)未曾被訪問(wèn)的頂點(diǎn)作起始點(diǎn),重復(fù)上述過(guò)程,直至圖中所有頂點(diǎn)都被訪問(wèn)到為止。流程圖

14、:出隊(duì)while(QueueLeDeQueue(&Queue,&n(&Queue);Vertex);定義訪問(wèn)標(biāo)志數(shù)組初始化訪問(wèn)標(biāo)志數(shù)組為false定義隊(duì)列、并初始化隊(duì)列if(InitQueue(&Queue,pGraph-VexNum)=FAILURE)否if(!VisitVertex)printf(ttt%s景點(diǎn) .n,pGraph-VexsVertex);標(biāo)志訪問(wèn)過(guò)VisitVertex=true;i=0iVexNum是if(Visiti=false&pGraph-否i+ArcsVertexi!=INF)是EnQueue(&Queue,i);終止程序:/ 輸出景區(qū)導(dǎo)游線路圖 ( 注:廣度優(yōu)

15、先遍歷 ) STATUS TraverseGraph(const PGRAPH pGraph)printf(ttt_n);printf(nttt$t輸出景區(qū)導(dǎo)游線路圖t$n);printf(ttt_nn);/ 定義訪問(wèn)標(biāo)志數(shù)組bool* Visit=(bool*)malloc(pGraph-VexNum*sizeof(bool);/ 初始化訪問(wèn)標(biāo)志數(shù)組為 false for(int i=0;iVexNum;i+) Visiti=false;/ 定義隊(duì)列、并初始化隊(duì)列QUEUE Queue; if(InitQueue(&Queue,pGraph-VexNum)=FAILURE)printf(tt

16、t警告:創(chuàng)建隊(duì)列失??! ! n);printf(ttt按任意鍵回主菜單! ! );getch();return FAILURE;/ 定義訪問(wèn)頂點(diǎn)變量,并初始值為0int Vertex=0;doif(!VisitVertex)printf(ttt%s景點(diǎn) .n,pGraph-VexsVertex);/ 標(biāo)志訪問(wèn)過(guò)VisitVertex=true;/ 遍歷與 Vertex 相連的頂點(diǎn)并進(jìn)隊(duì) for(i=0;iVexNum;i+)if(Visiti=false&pGraph-ArcsVertexi!=INF)EnQueue(&Queue,i);/ 出隊(duì)DeQueue(&Queue,&Vertex);

17、while(QueueLen(&Queue);/ 銷毀隊(duì)列DestroyQueue(&Queue);printf(ttt按任意鍵回主菜單! ! );getch();return SUCCESS;有向圖的拓?fù)渑判蚝沃^“拓?fù)渑判颉???duì)有向圖進(jìn)行如下操作:假設(shè) G=(V, E)是一個(gè)具有n 個(gè)頂點(diǎn)的有向圖,V 中頂點(diǎn)序列vl , v2, vn 稱做一個(gè)拓?fù)湫蛄?(Topological Order),當(dāng)且僅當(dāng)該頂點(diǎn)序列滿足下列條件:若在有向圖G中存在從頂點(diǎn) vi 到 vj 的一條路徑,則在頂點(diǎn)序列中頂點(diǎn)vi 必須排在頂點(diǎn)vj 之前。 通常,在 AOV網(wǎng)中,將所有活動(dòng)排列成一個(gè)拓?fù)湫蛄械倪^(guò)程叫做拓?fù)渑?/p>

18、序(Topological Sort)。在 AOV網(wǎng)中不應(yīng)該出現(xiàn)有向環(huán)。因?yàn)榄h(huán)的存在意味著某項(xiàng)活動(dòng)將以自己為先決條件,顯然無(wú)法形成拓?fù)湫蛄?。判定網(wǎng)中是否存在環(huán)的方法:出現(xiàn)在它的拓?fù)溆行蛐蛄兄?,則該對(duì)有向圖構(gòu)造其頂點(diǎn)的拓?fù)溆行蛐蛄校珹OV網(wǎng)中一定不存在環(huán)。若網(wǎng)中所有頂點(diǎn)都例如:對(duì)于有向圖可求得拓?fù)溆行蛐蛄校篈 B C D或A C B DBADc例如 ,對(duì)學(xué)生選課工程圖進(jìn)行拓?fù)渑判駽1 , C2 , C3 , C4 , C5 , C6 , C,8 , C得到的拓?fù)溆行蛐蛄袨? , C7 或C 1 , C 8 , C9 , C2 , C5 , C3 , C4 ,C7, C6反之,對(duì)于下列有向圖不能求

19、得它的拓?fù)溆行蛐蛄?。因?yàn)閳D中存在一個(gè)回路B, C, D如何進(jìn)行?輸入 AOV網(wǎng)絡(luò)。令n為頂點(diǎn)個(gè)數(shù)。( 1)在 AOV網(wǎng)絡(luò)中選一個(gè)沒(méi)有直接前驅(qū)的頂點(diǎn),并輸出之;( 2)從圖中刪去該頂點(diǎn) , 同時(shí)刪去所有它發(fā)出的有向邊;重復(fù)以上步驟, 直到全部頂點(diǎn)均已輸出, 拓?fù)溆行蛐蛄行纬桑?拓?fù)渑判蛲瓿?;或圖中還有未輸出的頂點(diǎn),但已跳出處理循環(huán)。這說(shuō)明圖中還剩下一些頂點(diǎn),它們都有直接前驅(qū),再也找不到?jīng)]有前驅(qū)的頂點(diǎn)了。這時(shí)AOV網(wǎng)絡(luò)中必定存在有向環(huán)。在實(shí)現(xiàn)拓?fù)渑判虻乃惴ㄖ校?采用鄰接表作為有向圖的存儲(chǔ)結(jié)構(gòu),表,每個(gè)單鏈表有一個(gè)表頭結(jié)點(diǎn),在表頭結(jié)點(diǎn)中增加一個(gè)存放頂點(diǎn)入度的域每個(gè)頂點(diǎn)設(shè)置一個(gè)單鏈count ,這些表

20、頭結(jié)點(diǎn)構(gòu)成一個(gè)數(shù)組。為了避免重復(fù)檢測(cè)入度為0 的點(diǎn),另設(shè)一棧存放所有入度為0 的點(diǎn)。對(duì)于有 n 個(gè)頂點(diǎn)和e 條邊的有向圖而言, for循環(huán)中建立入度為0 的頂點(diǎn)棧時(shí)間為若在拓?fù)渑判蜻^(guò)程中不出現(xiàn)有向環(huán),則每個(gè)頂點(diǎn)出棧、入棧和入度減1 的操作在while語(yǔ)句中均執(zhí)行e 次,因此拓?fù)渑判蚩偟臅r(shí)間花費(fèi)為O (n+e) 。(On);循環(huán)流程圖 :計(jì)算各頂點(diǎn)的入度j=0jVexNumi=0iVexNumif(pGraph-j+Arcsij!=INF)Indegreej+;if(!Indegreei+j)PushStack(&Stack,j);while(StackLen(&Stack)出桟、并訪問(wèn)PopS

21、tack(&Stack,&k);i=0iVexNumif(pGraph-Arcski!=i+INF)if(!(-Indegreei)PushStack(&Stack,i);程序 :/ 有向圖的拓?fù)渑判騍TATUS TopologicalSort(const PGRAPH pGraph)printf(ttt_n);printf(nttt$t導(dǎo)游線路圖有無(wú)回路t$n);printf(ttt_nn);/ 定義入度數(shù)組 , 記錄每個(gè)頂點(diǎn)的入度,初始化為 0 int IndegreeMAXNUM=0;/ 定義桟、并初始化桟STACK Stack;if(InitStack(&Stack,pGraph-Ve

22、xNum)=FAILURE)printf(ttt警告:創(chuàng)建桟失??! ! n);printf(ttt按任意鍵回主菜單! ! );getch();return FAILURE;printf(ttt計(jì)算各頂點(diǎn)的入度.n);for(int j=0;jVexNum;j+)/ 求各個(gè)頂點(diǎn)的入度f(wàn)or(int i=0;iVexNum;i+)if(pGraph-Arcsij!=INF)Indegreej+;/ 入度為 0 的頂點(diǎn)入棧if(!Indegreej)PushStack(&Stack,j);printf(ttt進(jìn)行拓?fù)渑判?n);/Count用來(lái)指示入度為0 的頂點(diǎn)個(gè)數(shù)int Count=0,k;wh

23、ile(StackLen(&Stack)/ 出桟、并訪問(wèn)PopStack(&Stack,&k); printf(%st,pGraph-Vexsk); Count+;/ 對(duì)出棧的頂點(diǎn)所指向的頂點(diǎn)減一,并且將入度為0 的頂點(diǎn)入棧for(int i=0;iVexNum;i+)if(pGraph-Arcski!=INF)if(!(-Indegreei)PushStack(&Stack,i);/ 銷毀桟DestroyStack(&Stack);/ 判斷是否是拓?fù)渑判騣f(CountVexNum)printf(ttt結(jié)果:導(dǎo)游線路圖有回路n);elseprintf(ttt結(jié)果:導(dǎo)游線路圖無(wú)回路n);pri

24、ntf(ttt按任意鍵回主菜單! ! );getch();return SUCCESS;求兩個(gè)景點(diǎn)間的最短路徑最短路徑定義所謂最短路徑問(wèn)題是指:如果從圖中某一頂點(diǎn)(源點(diǎn))到達(dá)另一頂點(diǎn)(終點(diǎn))的路徑可能不止一條, 如何找到一條路徑似的沿此路徑上各邊的權(quán)值總和(稱為路徑長(zhǎng)度) 達(dá)到最小。迪杰斯特拉 (Dijkstra)算法求單源最短路徑由 Dijkstra 提出的一種按路徑長(zhǎng)度遞增序產(chǎn)生各頂點(diǎn)最短路徑的算法。( 1)按路徑長(zhǎng)度遞增序產(chǎn)生各頂點(diǎn)最短路徑若按長(zhǎng)度遞增的次序生成從源點(diǎn)s 到其它頂點(diǎn)的最短路徑,則當(dāng)前正在生成的最短路徑上除終點(diǎn)以外, 其余頂點(diǎn)的最短路徑均已生成(將源點(diǎn)的最短路徑看作是已生成

25、的源點(diǎn)到其自身的長(zhǎng)度為0 的路徑)。( 2)具體做法一開(kāi)始第一組只包括頂點(diǎn)v 1 ,第二組包括其他所有頂點(diǎn),v 1 對(duì)應(yīng)的距離值為0,第二組的頂點(diǎn)對(duì)應(yīng)的距離值是這樣確定的:若圖中有邊,則v j的距離為此邊所帶的權(quán)值,否則v j的距離值為一個(gè)很大的數(shù)(大于所有頂點(diǎn)間的路徑長(zhǎng)度),然后每次從第二組的頂點(diǎn)中選一個(gè)其距離值為最小的v m加入到第一組中。每往第一組加入一個(gè)頂點(diǎn)v m ,就要對(duì)第二組的各個(gè)頂點(diǎn)的距離值進(jìn)行一次修正。若加進(jìn)v m 做中間頂點(diǎn),使從v 1到v j的最短路徑比不加v m的路徑為短,則要修改v j的距離值。修改后再選距離最小的頂點(diǎn)加入到第一組中。如此進(jìn)行下去,直到圖中所有頂點(diǎn)都包括

26、在第一組中,或再也沒(méi)有可加入到第一組中的頂點(diǎn)存在為止。假設(shè)有向圖 G的 n個(gè)頂點(diǎn)為 1 到 n,并用鄰接矩陣cost 表示 , 若 是圖 G 中的邊,則costij的值等于邊所帶的權(quán) ;若 不是圖 G 中的邊,則 costij等于一個(gè)很大的數(shù);若i=j,則 costij=0。另外, 設(shè)置三個(gè)數(shù)組 Sn 、 distn、 pren。 S 用以標(biāo)記那些已經(jīng)找到最短路徑的頂點(diǎn),若 Si-1=1,則表示已經(jīng)找到源點(diǎn)到頂點(diǎn)i的最短路徑 ,若 Si-1=0,則表示從源點(diǎn)到頂點(diǎn) i 的最短路徑尚未求得。disti-1用來(lái)記錄源點(diǎn)到頂點(diǎn)i 的最短路徑。 prei-1表示從源點(diǎn)到頂點(diǎn) i 的最短路徑上該點(diǎn)的前趨

27、頂點(diǎn),若從源點(diǎn)到該頂點(diǎn)無(wú)路徑,則用 0作為其前一個(gè)頂點(diǎn)序號(hào)。流程圖 :定義路徑矩陣、距離矩陣ADJMATRIXPathMatrix,DisMatrix;初始化路徑矩陣、距離矩陣i=0iVexNumj=0jVexNumj+DisMatrixij=pGraph-Arcsij;PathMatrixij=-1;求PathMatrix矩陣K=0kVexNumi=0iVexNumj=0jVexNumif(DisMatrixiji+DisMatrixik+DisMatrixkj)DisMatrixij=DisMatrixik+DisMatrixkj;j+PathMatrixij=k;程序 :/ 求兩個(gè)景點(diǎn)間

28、的最短路徑STATUS MinShortPath(const PGRAPH pGraph)printf(ttt_n);printf(nttt$t景點(diǎn)之間的最短路徑t$n);printf(ttt_nn);/ 定義路徑矩陣、距離矩陣ADJMATRIX PathMatrix,DisMatrix;/ 定義輔助變量int i,j,k;/ 初始化路徑矩陣、距離矩陣for(i=0;iVexNum;i+)for(j=0;jVexNum;j+)DisMatrixij=pGraph-Arcsij;PathMatrixij=-1;/ 求 PathMatrix矩陣for(k=0;kVexNum;k+)for(i=0;

29、iVexNum;i+)for(j=0;jVexNum;j+)if(DisMatrixijDisMatrixik+DisMatrixkj)DisMatrixij=DisMatrixik+DisMatrixkj;PathMatrixij=k;/ 定義起點(diǎn)、終點(diǎn)int Stav=-1,Endv=-1;/ 定義起點(diǎn)、終點(diǎn)名稱char StaNamMAXNUM,EndNamMAXNUM;printf(ttt輸入起始點(diǎn)和終點(diǎn)名稱( 格式:Sta End): );scanf(%s%s,StaNam,EndNam);for(i=0;iVexNum;i+)if(!strcmp(pGraph-Vexsi,StaN

30、am)/ 起始點(diǎn)名稱下標(biāo)Stav=i;if(!strcmp(pGraph-Vexsi,EndNam)/ 終點(diǎn)名稱下標(biāo)Endv=i;/ 判斷起始點(diǎn)名稱和終點(diǎn)名稱是否存在if(Stav=-1|Endv=-1)return FAILURE;/ 定義桟、并初始化STACK Stack;if(InitStack(&Stack,pGraph-VexNum)=FAILURE)printf(ttt警告:創(chuàng)建桟失??! ! n);printf(ttt按任意鍵回主菜單! ! );getch();/ 將所有路徑入桟while(Endv!=-1)/ 將所有路徑出桟、并輸出 printf(ttt);while(1)pri

31、ntf(%s-,pGraph-VexsStav);if(!StackLen(&Stack)break;PopStack(&Stack,&Stav);printf(終點(diǎn) );/ 銷毀桟DestroyStack(&Stack);printf(nttt按任意鍵回主菜單! ! );getch();return SUCCESS;輸出道路修建規(guī)劃圖prim 算法在無(wú)向加權(quán)圖中,n 個(gè)頂點(diǎn)的最小生成樹(shù)有n-1的代價(jià)最小。prim 算法是一種貪心算法,將全部的頂點(diǎn)劃分為條邊,這些邊使得n 個(gè)頂點(diǎn)之間可達(dá),且總2 個(gè)集合,每次總在2 個(gè)集合之間中找最小的一條邊,局部最優(yōu)最終達(dá)到全局最優(yōu),這正是貪心的思想。具體的

32、描述參見(jiàn)相關(guān)書(shū)籍:描述從單一頂點(diǎn)開(kāi)始, 普里姆算法按照以下步驟逐步擴(kuò)大樹(shù)中所含頂點(diǎn)的數(shù)目,直到遍及連通圖的所有頂點(diǎn)。1.輸入:一個(gè)加權(quán)連通圖,其中頂點(diǎn)集合為V,邊集合為 E;2.初始化: Vnew = x,其中 x 為集合 V 中的任一節(jié)點(diǎn)(起始點(diǎn)) , Enew = ;3.重復(fù)下列操作,直到Vnew = V :1. 在集合 E 中選取權(quán)值最小的邊( u, v),其中 u 為集合 Vnew中的元素,而 v 則不是(如果存在有多條滿足前述條件即具有相同權(quán)值的邊,則可任意選取其中之一);2. 將 v 加入集合 Vnew中,將( u, v )加入集合 Enew中;4. 輸出:使用集合 Vnew和 E

33、new來(lái)描述所得到的最小生成樹(shù)。例如 :流程圖 :定義輔助數(shù)組變量CLOSEDGEClosedge;i=1iVexNumClosedge.Lowcosti=pGraph-ArcsMini;strcpy(Closedi+ge.Vexsi,pGraph-VexsMin);i=1iVexNum保存輔助數(shù)組中Closedge.Lowcost權(quán)值最小值查找第一個(gè)權(quán)值不是0 的位置查找輔助數(shù)組中最小值輸出信息選擇最小邊j=0jVexNumif(pGraph-ArcsMinjArcsMinj;j+strcpy(Closedge.Vexsj,pGraph-VexsMin);程序 :/ 輸出道路修建規(guī)劃圖 (

34、注:最小生成樹(shù) ) STATUS MininumCST(const PGRAPH pGraph)printf(ttt_n);printf(nttt$t 輸出道路修建規(guī)劃圖 t$n); printf(ttt_nn);/ 定義輔助數(shù)組變量CLOSEDGE Closedge;int Min=0;/ 初始化輔助數(shù)組 , 從第一個(gè)頂點(diǎn)開(kāi)始for(int i=1;iVexNum;i+)Closedge.Lowcosti=pGraph-ArcsMini;strcpy(Closedge.Vexsi,pGraph-VexsMin);Closedge.LowcostMin=0;/ 選這其余的 pGraph-VexNum-1 個(gè)點(diǎn) for(i=1;iVexNum;i+)/ 保存輔助數(shù)組中 Closedge.Lowcost 權(quán)值最小值/ 查找第一個(gè)權(quán)值不是 0 的位置for(int j=0;jVexNum;j+)if(Closedge.Lowcostj!=0)break;Min=j;/ 查找輔助數(shù)組中最小值for(j=0;jVexNum;j+)if(C

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝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ù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(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ì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論