景區(qū)旅游信息管理系統(tǒng)

word文檔精品文檔分享校園旅游信息管理系統(tǒng)1.1工程需求分析在旅游景區(qū)，經(jīng)常會(huì)遇到游客打聽(tīng)從一個(gè)景點(diǎn)到另一個(gè)景點(diǎn)的最短路徑和最短距離，這類(lèi)游客不喜歡按照導(dǎo)游圖的線路來(lái)游覽，而是摘要自己感興趣的景點(diǎn)游覽。為于幫助這類(lèi)游客信息查詢(xú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)游線路圖用有向圖表示。遍歷采用深度優(yōu)先策略，這也比較符合游客心理。〔〕為了使導(dǎo)游線路圖能夠優(yōu)化，可通過(guò)拓樸排序判斷圖中有無(wú)回路，假設(shè)有回路，那么打印輸出回路中的景點(diǎn)，供人工優(yōu)化。〔〕在導(dǎo)游線路圖中，還為一些不愿按線路走的游客提供信息效勞，比方從一個(gè)景點(diǎn)到另一個(gè)景點(diǎn)的最短路徑和最短距離。在本線路圖中將輸出任意景點(diǎn)間的最短路徑和最短距離?！病吃诰皡^(qū)建立中，道路建立是其中一個(gè)重要內(nèi)容。道路建立首先要保證能連通所有景點(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)游線路圖；判斷導(dǎo)游線路圖有無(wú)回路；求兩個(gè)景點(diǎn)間的最短路徑和最短距離；輸出道路修建規(guī)劃圖。主程序用菜單項(xiàng)選擇項(xiàng)供用戶(hù)選擇功能模塊。word文檔精品文檔分享1.2工程設(shè)計(jì)流程1.2.1工程總體框架校園旅游信息管理系統(tǒng)創(chuàng)輸輸導(dǎo)兩輸建出出游個(gè)出景景景線景道區(qū)區(qū)區(qū)路點(diǎn)路景景導(dǎo)圖間修點(diǎn)點(diǎn)游有的建分分線無(wú)最規(guī)布布路回短劃圖圖圖路路圖word文檔精品文檔分享1.2.2工程數(shù)據(jù)構(gòu)造#ifndefSUCCESS//標(biāo)志位成功#defineSUCCESS1#endif#ifndefFAILURE//標(biāo)志位失敗#defineFAILURE0#endif#ifndefINF//標(biāo)志位無(wú)窮#defineINF0x3f3fffff#endif#ifndefMAXNUM#defineMAXNUM20#endiftypedefboolSTATUS;//定義函數(shù)狀態(tài)數(shù)據(jù)類(lèi)型typedefcharVERTEXTYPE[MAXNUM][11];//定義頂點(diǎn)向量數(shù)據(jù)類(lèi)型typedefintADJMATRIX[MAXNUM][MAXNUM];//定義鄰接矩陣數(shù)據(jù)類(lèi)型typedefstructGRAPH//定義圖數(shù)據(jù)類(lèi)型{VERTEXTYPEVexs;//圖的頂點(diǎn)向量ADJMATRIXArcs;//圖的鄰接矩陣intVexNum;//圖的當(dāng)前頂點(diǎn)intArcNum;//圖的當(dāng)前弧}*PGRAPH;//定義圖的指針數(shù)據(jù)類(lèi)型typedefstructCLOSEDGE//定義輔助數(shù)組數(shù)據(jù)類(lèi)型{VERTEXTYPEVexs;//圖的頂點(diǎn)向量intLowcost[MAXNUM];//}*PCLOSEDGE;//定義輔助數(shù)組指針數(shù)據(jù)類(lèi)型word文檔精品文檔分享1.2.3工程模塊設(shè)計(jì)創(chuàng)立景區(qū)景點(diǎn)分布圖一.鄰接矩陣(Adjacency二維數(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.edge[n][n]，定義(滿足如下條件的n階矩陣)：][j]0,if(<i,j>Eor(i,j)Eotherwise)無(wú)向圖數(shù)組表示法特點(diǎn)：1〕無(wú)向圖鄰接矩陣是對(duì)稱(chēng)矩陣，同一條邊表示了兩次；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或清；2；G占用存儲(chǔ)空間5〕設(shè)存儲(chǔ)頂點(diǎn)的一維數(shù)組大小為n(圖的頂點(diǎn)數(shù)n),G占用存儲(chǔ)空間：n+n只與它的頂點(diǎn)數(shù)有關(guān)，與邊數(shù)無(wú)關(guān)；適用于邊稠密的圖；流程圖：初始化圖的頂點(diǎn)數(shù)scanf("%d",&pGraph->VexNum);if(pGraph->VexNum>20)初始化圖的弧數(shù)scanf("%d",&pGraph->ArcNum);if(pGraph->ArcNum>20)初始化圖的頂點(diǎn)名稱(chēng)初始化圖的弧權(quán)值為最大值輸入弧的信息終止word文檔精品文檔分享程序：//創(chuàng)立景區(qū)景點(diǎn)分布圖STATUSCreateGraph(PGRAPHpGraph){printf("\t\t\t_________________________________\n");printf("\n\t\t\t$\t創(chuàng)立景區(qū)景點(diǎn)分布圖\t$\n");printf("\t\t\t_________________________________\n");//初始化圖的頂點(diǎn)數(shù)printf("\t\t\t初始化頂點(diǎn)數(shù)和弧度數(shù)......\n");printf("\t\t\t請(qǐng)輸入圖的頂點(diǎn)數(shù)：");scanf("%d",&pGraph->VexNum);//檢查if(pGraph->VexNum>20){printf("\t\t\t警告：輸入數(shù)據(jù)錯(cuò)誤！\n");printf("\t\t\t按任意鍵回主菜單！");getch();returnFAILURE;}//初始化圖的弧數(shù)printf("\t\t\t請(qǐng)輸入圖的弧度數(shù)：");scanf("%d",&pGraph->ArcNum);//檢查if(pGraph->ArcNum>20){printf("\t\t\t警告：輸入數(shù)據(jù)錯(cuò)誤！\n");printf("\t\t\t按任意鍵回主菜單！");getch();returnFAILURE;}//初始化圖的頂點(diǎn)名稱(chēng)printf("\t\t\t---------------------------------\n");printf("\t\t\t初始化的頂點(diǎn)名稱(chēng)......\n");for(inti=0;i<pGraph->VexNum;i++){printf("\t\t\t請(qǐng)輸入第%d個(gè)頂點(diǎn)名稱(chēng)：",i+1);scanf("%s",pGraph->Vexs[i]);}//初始化圖的弧權(quán)值為最大值for(i=0;i<pGraph->VexNum;i++)for(intj=0;j<pGraph->VexNum;j++)word文檔精品文檔分享pGraph->Arcs[i][j]=INF;//輸入弧的信息printf("\t\t\t---------------------------------\n");printf("\t\t\t初始化的弧的信息......\n");printf("\t\t\t請(qǐng)輸入弧的信息(注：從0開(kāi)場(chǎng))：\n");for(i=0;i<pGraph->ArcNum;i++){intStav,Endv,Weight;printf("\t\t\t請(qǐng)輸入第%d條弧(格式：ViVjWeight)：",i+1);scanf("%d%d%d",&Stav,&Endv,&Weight);pGraph->Arcs[Endv][Stav]=Weight;pGraph->Arcs[Stav][Endv]=Weight;}printf("\t\t\t創(chuàng)立景區(qū)景點(diǎn)分布圖成功！\n");printf("\t\t\t按任意鍵回主菜單！");getch();returnSUCCESS;}輸出景區(qū)景點(diǎn)分布圖流程圖：word文檔精品文檔分享景區(qū)景點(diǎn)名稱(chēng)i=0i<pGraph->VexNumt",pGraph->Vexs[i]);i++景區(qū)景點(diǎn)信息i=0i<pGraph->VexNum終止j=0i++j<pGraph->VexNumif(pGraph->Arcs[i][j]==INF)t",pGraph->Arcs[i][j]);j++printf("∞\t");程序：//輸出景區(qū)景點(diǎn)分布圖STATUSPrintGraph(constPGRAPHpGraph){printf("\t\t\t_________________________________\n");printf("\n\t\t\t$\t顯示景區(qū)景點(diǎn)分布圖\t$\n");printf("\t\t\t_________________________________\n\n");//printf("\t景區(qū)景點(diǎn)名稱(chēng)......\n\t");for(inti=0;i<pGraph->VexNum;i++)printf("%s\t",pGraph->Vexs[i]);printf("\n\n\t景區(qū)景點(diǎn)信息......\n");word文檔精品文檔分享for(i=0;i<pGraph->VexNum;i++){printf("\t___________________________________________________________\n\t");for(intj=0;j<pGraph->VexNum;j++)if(pGraph->Arcs[i][j]==INF)printf("∞\t");elseprintf("%d\t",pGraph->Arcs[i][j]);printf("\n");}printf("\t___________________________________________________________\n\t");printf("按任意鍵回主菜單！");getch();returnSUCCESS;}輸出景區(qū)導(dǎo)游線路圖圖的遍歷從圖中某一頂點(diǎn)出發(fā)訪遍圖中所有的頂點(diǎn)，且使每個(gè)頂點(diǎn)僅被訪問(wèn)一次，這一過(guò)程就叫做圖的遍歷(Traversing。圖中可能存在回路，且圖的任一頂點(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(DepthFirstSearch)廣度優(yōu)先搜索BFS(BreadthFirstSearch)廣度優(yōu)先搜索遍歷圖(BFS)對(duì)連通圖，從起始點(diǎn)V到其余各頂點(diǎn)必定存在路徑。其中，,V->w2,V->w8的路徑長(zhǎng)度為1;V->w,V->w,V->w5的路徑長(zhǎng)度為2;V->w,V->w4的路徑長(zhǎng)度為3word文檔精品文檔分享從圖中的某個(gè)頂點(diǎn)0出發(fā)，并在訪問(wèn)此頂點(diǎn)之后依次訪問(wèn)0的所有未被訪問(wèn)過(guò)的鄰接點(diǎn)，之后按這些頂點(diǎn)被訪問(wèn)的先后次序依次訪問(wèn)它們的鄰接點(diǎn)，直至圖中所有和0有路徑相通的頂點(diǎn)都被訪問(wèn)到。假設(shè)此時(shí)圖XX有頂點(diǎn)未被訪問(wèn)那么另選圖中一個(gè)未曾被訪問(wèn)的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)都被訪問(wèn)到為止。流程圖：word文檔精品文檔分享定義訪問(wèn)標(biāo)志數(shù)組初始化訪問(wèn)標(biāo)志數(shù)組為false定義隊(duì)列、并初始化隊(duì)列if(InitQueue(&Queue,pGraph->VexNum)==FAILURE)否while(QueueLen(&Queue));出隊(duì)DeQueue(&Queue,&Vertex);if(!Visit[Vertex])printf("\t\t\t%s景點(diǎn)......\n",pGraph->Vexs[Vertex]);標(biāo)志訪問(wèn)過(guò)Visit[Vertex]=true;i=0i<pGraph->VexNum是if(Visit[i]==false&&pGraph->Arcs[Vertex][i]!=INF)否i++是EnQueue(&Queue,i);終止程序：//輸出景區(qū)導(dǎo)游線路圖(注：廣度優(yōu)先遍歷)STATUSTraverseGraph(constPGRAPHpGraph){printf("\t\t\t_________________________________\n");printf("\n\t\t\t$\t輸出景區(qū)導(dǎo)游線路圖\t$\n");printf("\t\t\t_________________________________\n\n");//定義訪問(wèn)標(biāo)志數(shù)組bool*Visit=(bool*)malloc(pGraph->VexNum*sizeof(bool));//初始化訪問(wèn)標(biāo)志數(shù)組為falsefor(inti=0;i<pGraph->VexNum;i++)word文檔精品文檔分享Visit[i]=false;//定義隊(duì)列、并初始隊(duì)列QUEUEQueue;if(InitQueue(&Queue,pGraph->VexNum)==FAILURE){printf("\t\t\t警告：創(chuàng)立隊(duì)列\(zhòng)n");printf("\t\t\t按任意鍵回主菜！");getch();returnFAILURE;}//定義訪問(wèn)頂點(diǎn)變，并初始為0intVertex=0;do{if(!Visit[Vertex]){printf("\t\t\t%s景點(diǎn)......\n",pGraph->Vexs[Vertex]);//標(biāo)訪問(wèn)過(guò)Visit[Vertex]=true;//遍歷Vertex相連的頂點(diǎn)并進(jìn)隊(duì)for(i=0;i<pGraph->VexNum;i++)if(Visit[i]==false&&pGraph->Arcs[Vertex][i]!=INF)EnQueue(&Queue,i);}//出隊(duì)DeQueue(&Queue,&Vertex);}while(QueueLen(&Queue));//銷(xiāo)隊(duì)列DestroyQueue(&Queue);printf("\t\t\t按任意鍵回主菜！");getch();returnSUCCESS;}有向圖的拓?fù)渑判蚝沃^“拓?fù)渑判颞?？?duì)有向圖進(jìn)展如下:假G=(V，E)是一個(gè)具有n個(gè)頂點(diǎn)的有向圖，V中頂點(diǎn)序列vl，v2，?，vn稱(chēng)做一個(gè)拓?fù)湫蛄?TopologicalOrder)，當(dāng)且僅當(dāng)該頂點(diǎn)序列滿足以下條件：在有向圖G中存在從word文檔精品文檔分享頂點(diǎn)vi到vj的一條路徑，那么在頂點(diǎn)序列中頂點(diǎn)vi必須排在頂點(diǎn)vj之前。通常，在AOV網(wǎng)中，將所有活動(dòng)排列成一個(gè)拓?fù)湫蛄械倪^(guò)程叫做拓?fù)渑判?TopologicalSort)。在AOV網(wǎng)中不應(yīng)該出現(xiàn)有向環(huán)。因?yàn)榄h(huán)的存在意味著某項(xiàng)活動(dòng)將以自己為先決條件，顯然無(wú)法形成拓?fù)湫蛄?。判定網(wǎng)中是否存在環(huán)的方法：對(duì)有向圖構(gòu)造其頂點(diǎn)的拓?fù)溆行蛐蛄?，假設(shè)網(wǎng)中所有頂點(diǎn)都出現(xiàn)在它的拓?fù)溆行蛐蛄兄校敲丛揂OV網(wǎng)中一定不存在環(huán)。例如：對(duì)于有向圖可求得拓?fù)溆行蛐蛄校篈BCD或ACBDBADc例如,對(duì)學(xué)生選課工程圖進(jìn)展拓?fù)渑判?得到的拓?fù)溆行蛐蛄袨?,2,3,4,5,6,8,9,7或1,8,9,2,5,3,4,7,6反之，對(duì)于以下有向圖word文檔精品文檔分享不能求得它的拓?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ǔ)構(gòu)造，每個(gè)頂點(diǎn)設(shè)置一個(gè)單鏈表，每個(gè)單鏈表有一個(gè)表頭結(jié)點(diǎn)，在表頭結(jié)點(diǎn)中增加一個(gè)存放頂點(diǎn)入度的域count，這些表頭結(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í)間為O〔n〕；假設(shè)在拓?fù)渑判蜻^(guò)程中不出現(xiàn)有向環(huán)，那么每個(gè)頂點(diǎn)出棧、入棧和入度減1的操作在while循環(huán)語(yǔ)句中均執(zhí)行e次，因此拓?fù)渑判蚩偟臅r(shí)間花費(fèi)為O(n+e)。流程圖:計(jì)算各頂點(diǎn)的入度j=0j<pGraph->VexNumi=0i<pGraph->VexNumif(pGraph-j++>Arcs[i][j]!=INF)Indegree[j]++;if(!Indegree[i++j])PushStack(&Stack,j);word文檔精品文檔分享while(StackLen(&Stack))出桟、并訪問(wèn)PopStack(&Stack,&k);i=0i<pGraph->VexNumif(pGraph->Arcs[k][i]!=INF)i++if(!(--Indegree[i]))PushStack(&Stack,i);程序://有向圖的拓?fù)渑判騍TATUSTopologicalSort(constPGRAPHpGraph){printf("\t\t\t_________________________________\n");printf("\n\t\t\t$\t導(dǎo)游線路圖有無(wú)回路\t$\n");printf("\t\t\t_________________________________\n\n");//定義入度數(shù)組,記錄每個(gè)頂點(diǎn)的入度，初始化為0intIndegree[MAXNUM]={0};//定義桟、并初始化桟STACKStack;if(InitStack(&Stack,pGraph->VexNum)==FAILURE){printf("\t\t\t警告：創(chuàng)立桟失敗！\n");printf("\t\t\t按任意鍵回主菜單！");getch();returnFAILURE;}printf("\t\t\t計(jì)算各頂點(diǎn)的入度.....\n");for(intj=0;j<pGraph->VexNum;j++){word文檔精品文檔分享//求各個(gè)頂點(diǎn)的入度f(wàn)or(inti=0;i<pGraph->VexNum;i++)if(pGraph->Arcs[i][j]!=INF)Indegree[j]++;//入度為0的頂點(diǎn)入棧if(!Indegree[j])PushStack(&Stack,j);}printf("\t\t\t進(jìn)展拓?fù)渑判?....\n");//Count用來(lái)指示入度為0的頂點(diǎn)個(gè)數(shù)intCount=0,k;while(StackLen(&Stack)){//出桟、并訪問(wèn)PopStack(&Stack,&k);printf("%s\t",pGraph->Vexs[k]);Count++;//對(duì)出棧的頂點(diǎn)所指向的頂點(diǎn)減一，并且將入度為0的頂點(diǎn)入棧for(inti=0;i<pGraph->VexNum;i++)if(pGraph->Arcs[k][i]!=INF)if(!(--Indegree[i]))PushStack(&Stack,i);}//銷(xiāo)毀桟DestroyStack(&Stack);//判斷是否是拓?fù)渑判騣f(Count<pGraph->VexNum)printf("\t\t\t結(jié)果：導(dǎo)游線路圖有回路\n");elseprintf("\t\t\t結(jié)果：導(dǎo)游線路圖無(wú)回路\n");printf("\t\t\t按任意鍵回主菜單！");getch();returnSUCCESS;}求兩個(gè)景點(diǎn)間的最短路徑最短路徑定義所謂最短路徑問(wèn)題是指：如果從圖中某一頂點(diǎn)〔源點(diǎn)〕到達(dá)另一頂點(diǎn)〔終點(diǎn)〕的路徑可能不止一條，如何找到一條路徑似的沿此路徑上各邊的權(quán)值總和〔稱(chēng)為路徑長(zhǎng)度〕到達(dá)最小。word文檔精品文檔分享迪杰斯特拉(Dijkstra)算法求單源最短路徑由Dijkstra提出的一種按路徑長(zhǎng)度遞增序產(chǎn)生各頂點(diǎn)最短路徑的算法?！病嘲绰窂介L(zhǎng)度遞增序產(chǎn)生各頂點(diǎn)最短路徑假設(shè)按長(zhǎng)度遞增的次序生成從源點(diǎn)s到其它頂點(diǎn)的最短路徑，那么當(dāng)前正在生成的最短路徑上除終點(diǎn)以外，其余頂點(diǎn)的最短路徑均已生成〔將源點(diǎn)的最短路徑看作是已生成的源點(diǎn)到其自身的長(zhǎng)度為0的路徑〕。〔〕具體做法一開(kāi)場(chǎng)第一組只包括頂點(diǎn)v1，第二組包括其他所有頂點(diǎn)，v1對(duì)應(yīng)的距離值為0，第二組的頂點(diǎn)對(duì)應(yīng)的距離值是這樣確定的：假設(shè)圖中有邊<v1,vj>,那么vj的距離為此邊所帶的權(quán)值，否那么vj的距離值為一個(gè)很大的數(shù)(大于所有頂點(diǎn)間的路徑長(zhǎng)度)，然后每次從第二組的頂點(diǎn)中選一個(gè)其距離值為最小的vm參加到第一組中。每往第一組參加一個(gè)頂點(diǎn)vm，就要對(duì)第二組的各個(gè)頂點(diǎn)的距離值進(jìn)展一次修正。假設(shè)加進(jìn)vm做中間頂點(diǎn)，使從v1到vj的最短路徑比不加vm的路徑為短，那么要修改vj的距離值。修改后再選距離最小的頂點(diǎn)參加到第一組中。如此進(jìn)展下去，直到圖中所有頂點(diǎn)都包括在第一組中，或再也沒(méi)有可參加到第一組中的頂點(diǎn)存在為止。假設(shè)有向圖G的n個(gè)頂點(diǎn)為1到n,并用鄰接矩陣cost表示,假設(shè)<vi,vj>是圖G中的邊，那么cost[i][j]的值等于邊所帶的權(quán);假設(shè)<vi,vj>不是圖G中的邊，那么cost[i][j]等于一個(gè)很大的數(shù)；假設(shè)i=j,那么cost[i][j]=0,設(shè)置三個(gè)數(shù)組S[n]、dist[n]、pre[n]。S用以標(biāo)記那些已經(jīng)找到最短路徑的頂點(diǎn)，假設(shè)S[i-1]=1,那么表示已經(jīng)找到源點(diǎn)到頂點(diǎn)i的最短路徑,假設(shè)S[i-1]=0,那么表示從源點(diǎn)到頂點(diǎn)i的最短路徑尚未求得。dist[i-1]用來(lái)記錄源點(diǎn)到頂點(diǎn)i的最短路徑。pre[i-1]表示從源點(diǎn)到頂點(diǎn)i的最短路徑上該點(diǎn)的前趨頂點(diǎn)，假設(shè)從源點(diǎn)到該頂點(diǎn)無(wú)路徑，那么用0作為其前一個(gè)頂點(diǎn)序號(hào)。流程圖:word文檔精品文檔分享定義路徑矩陣、距離矩陣ADJMATRIXPathMatrix,DisMatrix;初始化路徑矩陣、距離矩陣i=0i<pGraph->VexNumj=0i++j<pGraph->VexNumj++DisMatrix[i][j]=pGraph->Arcs[i][j];PathMatrix[i][j]=-1;求PathMatrix矩陣K=0k<pGraph->VexNumi=0i<pGraph->VexNumK++j=0j<pGraph->VexNumif(DisMatrix[i][j]>i++DisMatrix[i][k]+DisMatrix[k][j])DisMatrix[i][j]=DisMatrix[i][k]+DisMatrix[k][j];PathMatrix[i][j]=k;j++word文檔精品文檔分享程序://求兩個(gè)景點(diǎn)間的最短路徑STATUSMinShortPath(constPGRAPHpGraph){printf("\t\t\t_________________________________\n");printf("\n\t\t\t$\t景點(diǎn)之間的最短路徑\t$\n");printf("\t\t\t_________________________________\n\n");//定義路徑矩陣、距離矩陣ADJMATRIXPathMatrix,DisMatrix;//定義輔助變量inti,j,k;//初始化路徑矩陣、距離矩陣for(i=0;i<pGraph->VexNum;i++)for(j=0;j<pGraph->VexNum;j++){DisMatrix[i][j]=pGraph->Arcs[i][j];PathMatrix[i][j]=-1;}//求PathMatrix矩陣for(k=0;k<pGraph->VexNum;k++)for(i=0;i<pGraph->VexNum;i++)for(j=0;j<pGraph->VexNum;j++)if(DisMatrix[i][j]>DisMatrix[i][k]+DisMatrix[k][j]){DisMatrix[i][j]=DisMatrix[i][k]+DisMatrix[k][j];PathMatrix[i][j]=k;}//定義起點(diǎn)、終點(diǎn)intStav=-1,Endv=-1;//定義起點(diǎn)、終點(diǎn)名稱(chēng)charStaNam[MAXNUM],EndNam[MAXNUM];printf("\t\t\t輸入起始點(diǎn)和終點(diǎn)名稱(chēng)(格式：StaEnd)：");scanf("%s%s",StaNam,EndNam);for(i=0;i<pGraph->VexNum;i++){if(!strcmp(pGraph->Vexs[i],StaNam))//起始點(diǎn)名稱(chēng)下標(biāo)Stav=i;if(!strcmp(pGraph->Vexs[i],EndNam))//終點(diǎn)名稱(chēng)下標(biāo)word文檔精品文檔分享Endv=i;}//判斷起始點(diǎn)名稱(chēng)和終點(diǎn)名稱(chēng)是否存在if(Stav==-1||Endv==-1)returnFAILURE;//定義桟、并初始化STACKStack;if(InitStack(&Stack,pGraph->VexNum)==FAILURE){printf("\t\t\t警告：創(chuàng)立桟失??！\n");printf("\t\t\t按任意鍵回主菜單！");getch();}//將所有路徑入桟while(Endv!=-1){PushStack(&Stack,Endv);Endv=PathMatrix[Stav][Endv];}//將所有路徑出桟、并輸出printf("\t\t\t");while(1){printf("%s-->",pGraph->Vexs[Stav]);if(!StackLen(&Stack))break;PopStack(&Stack,&Stav);}printf("終點(diǎn)");//銷(xiāo)毀桟DestroyStack(&Stack);printf("\n\t\t\t按任意鍵回主菜單！");getch();returnSUCCESS;}輸出道路修建規(guī)劃圖prim算法在無(wú)向加權(quán)圖中，n個(gè)頂點(diǎn)的最小生成樹(shù)有n-1條邊，這些邊使得n個(gè)頂點(diǎn)之間可達(dá)，且總word文檔精品文檔分享的代價(jià)最小。prim算法是一種貪心算法，將全部的頂點(diǎn)劃分為2個(gè)集合，每次總在2個(gè)集合之間中找最小的一條邊，局部最優(yōu)最終到達(dá)全局最優(yōu)，這正是貪心的思想。具體的描述參見(jiàn)相關(guān)書(shū)籍：描述從單一頂點(diǎn)開(kāi)場(chǎng)，普里姆算法按照以下步驟逐步擴(kuò)大樹(shù)中所含頂點(diǎn)的數(shù)目，直到普及連通圖的所有頂點(diǎn)。1.輸入：一個(gè)加權(quán)連通圖，其中頂點(diǎn)集合為V，邊集合為；2.初始化：Vnew=，其中x為集合V中的任一節(jié)點(diǎn)〔起始點(diǎn)〕，Enew={}；3.重復(fù)以下操作，直到Vnew=：1.在集合E中選取權(quán)值最小的邊〔u,vu為集合Vnew中的元素，而v那么不是〔如果存在有多條滿足前述條件即具有一樣權(quán)值的邊，那么可任意選取其中之一〕；2.將v參加集合Vnew中，將〔u,〕參加集合Enew中；4.輸出：使用集合Vnew和Enew來(lái)描述所得到的最小生成樹(shù)。例如:流程圖:word文檔精品文檔分享定義輔助數(shù)組變量CLOSEDGEClosedge;i=1i<pGraph->VexNumClosedge.Lowcost[i]=pGraph->Arcs[Min][i];strcpy(Closedi++ge.Vexs[i],pGraph->Vexs[Min]);i=1i<pGraph->VexNum保存輔助數(shù)組中Closedge.Lowcost權(quán)值最小值查找第一個(gè)權(quán)值不是0的位置查找輔助數(shù)組中最小值輸出信息選擇最小邊j=0i++j<pGraph->VexNumif(pGraph->Arcs[Min][j]<Closedge.Lowcost[j])Closedge.Lowcost[j]=pGraph->Arcs[Min][j];strcpy(Closedge.Vexs[j],pGraph->Vexs[Min]);j++word文檔精品文檔分享程序://輸出道路修建規(guī)劃圖注：最小生成樹(shù))STATUSMininumCST(constPGRAPHpGraph){printf("\t\t\t_________________________________\n");printf("\n\t\t\t$\t輸出道路修建規(guī)劃圖\t$\n");printf("\t\t\t_________________________________\n\n");//定義輔助數(shù)組變量CLOSEDGEClosedge;intMin=0;//初始化輔助數(shù)組從第一個(gè)頂點(diǎn)開(kāi)場(chǎng)for(inti=1;i<pGraph->VexNum;i++){Closedge.Lowcost[i]=pGraph->Arcs[Min][i];strcpy(Closedge.Vexs[i],pGraph->Vexs[Min]);}Closedge.Lowcost[Min]=0;//選這其余的pGraph->VexNum-1個(gè)點(diǎn)for(i=1;i<pGraph->VexNum;i++){//保存輔助數(shù)組中Closedge.Lowcost權(quán)值最小值//查找第一個(gè)權(quán)值不是0的位置for(intj=0;j<pGraph->VexNum;j++)if(Closedge.Lowcost[j]!=0)break;Min=j;//查找輔助數(shù)組中最小值for(j=0;j<pGraph->VexNum;j++)if(Closedge.Lowcost[j]&&Closedge.Lowcost[j]<Closedge.Lowcost[Min])Min=j;//輸出信息printf("\t\t\t\t%s---->%s\n",Closedge.Vexs[Min],pGraph->Vexs[Min]);//Closedge.Lowcost[Min]=0;//選擇最小邊f(xié)or(j=0;j<pGraph->VexNum;j++)if(pGraph->Arcs[Min][j]<Closedge.Lowcost[j]){Closedge.Lowcost[j]=pGraph->Arcs[Min][j];strcpy(Closedge.Vexs[j],pGraph->Vexs[Min]);}}word文檔精品文檔分享printf("\n\t\t\t按任意鍵回主菜單！");getch();returnSUCCESS;}1.3工程編碼實(shí)現(xiàn)#include<stdio.h>#include<stdlib.h>#include"Graph.h"intFrame(){printf("\t\t\t_________________________________\n");printf("\n\t\t\t$\t景區(qū)旅游信息管理系統(tǒng)\t$\n");printf("\t\t\t_________________________________\n\n");printf