校園旅游信息管理系統1.1項目需求分析在旅游景區，經常會碰到游客打聽從一個景點到另一個景點的最短途徑和最短距離，這類游客不喜歡按照導游圖的線路來游覽，而是挑選自己感愛好的景點游覽。為于幫助這類游客信息查詢，就需要計算出所有景點之間最短途徑和最短距離。算法采用迪杰斯特拉算法或弗洛伊德算法均可。建立一個景區旅游信息管理系統，實現的重要功能涉及制訂旅游景點導游線路策略和制訂景區道路鋪設策略。任務中景點分布是一個無向帶權連通圖，圖中邊的權值是景點之間的距離。

1）景區旅游信息管理系統中制訂旅游景點導游線路策略，一方面通過遍歷景點，給出一個入口景點，建立一個導游線路圖，導游線路圖用有向圖表達。遍歷采用深度優先策略，這也比較符合游客心理。

（2）為了使導游線路圖可以優化，可通過拓樸排序判斷圖中有無回路，若有回路，則打印輸出回路中的景點，供人工優化。

（3）在導游線路圖中，還為一些不愿按線路走的游客提供信息服務，比如從一個景點到另一個景點的最短途徑和最短距離。在本線路圖中將輸出任意景點間的最短途徑和最短距離。

（4）在景區建設中，道路建設是其中一個重要內容。道路建設一方面要保證能連通所有景點，但又要花最小的代價，可以通過求最小生成樹來解決這個問題。本任務中假設修建道路的代價只與它的里程相關。因此歸納起來，本任務有如下功能模塊：

創建景區景點分布圖；

輸出景區景點分布圖（鄰接矩陣）

輸出導游線路圖；

判斷導游線路圖有無回路；

求兩個景點間的最短途徑和最短距離；

輸出道路修建規劃圖。

主程序用菜單選項供用戶選擇功能模塊。1.2項目設計流程1.2.1項目總體框架校園旅游信息管理系統校園旅游信息管理系統創建景區景點分布圖輸出景區景點分布圖輸出景區導游線路圖導游線路圖有無回路兩個景點間的最短路徑輸出道路修建規劃圖1.2.2項目數據結構#ifndefSUCCESS //標志位成功#defineSUCCESS 1#endif#ifndefFAILURE //標志位失敗#defineFAILURE 0#endif#ifndefINF //標志位無窮#defineINF 0x3f3fffff#endif#ifndefMAXNUM#defineMAXNUM 20#endiftypedefboolSTATUS; //定義函數狀態數據類型typedefcharVERTEXTYPE[MAXNUM][11]; //定義頂點向量數據類型typedefintADJMATRIX[MAXNUM][MAXNUM]; //定義鄰接矩陣數據類型typedefstructGRAPH //定義圖數據類型{ VERTEXTYPEVexs; //圖的頂點向量 ADJMATRIXArcs; //圖的鄰接矩陣 intVexNum; //圖的當前頂點 intArcNum; //圖的當前弧}*PGRAPH; //定義圖的指針數據類型typedefstructCLOSEDGE //定義輔助數組數據類型{ VERTEXTYPEVexs; //圖的頂點向量 intLowcost[MAXNUM]; //}*PCLOSEDGE; //定義輔助數組指針數據類型1.2.3項目模塊設計創建景區景點分布圖鄰接矩陣(AdjacencyMatrix)(二維數組表達法）在圖的鄰接矩陣表達中，有一個記錄各個頂點信息的頂點表，尚有一個表達各個頂點之間關系的鄰接矩陣。設圖A=(V,E)是一個有n個頂點的圖,圖的鄰接矩陣是一個二維數組A.edge[n][n]，定義(滿足如下條件的n階矩陣)：無向圖數組表達法特點：1）無向圖鄰接矩陣是對稱矩陣，同一條邊表達了兩次；2）頂點v的度：在無向圖中檔于二維數組相應行（或列）中1的個數；在有向圖中,記錄第i行1的個數可得頂點i的出度，記錄第j列1的個數可得頂點j的入度。3）判斷兩頂點v、u是否為鄰接點：只需判二維數組相應分量是否為1；4）頂點不變，在圖中增長、刪除邊：只需對二維數組相應分量賦值1或清0；5）設存儲頂點的一維數組大小為n(圖的頂點數n),G占用存儲空間：n+n2；G占用存儲空間只與它的頂點數有關，與邊數無關；合用于邊稠密的圖； 流程圖：程序：//創建景區景點分布圖STATUSCreateGraph(PGRAPHpGraph){ printf("\t\t\t_________________________________\n"); printf("\n\t\t\t$\t創建景區景點分布圖\t$\n"); printf("\t\t\t_________________________________\n"); //初始化圖的頂點數 printf("\t\t\t初始化頂點數和弧度數......\n"); printf("\t\t\t請輸入圖的頂點數(<=20)："); scanf("%d",&pGraph->VexNum); //檢查 if(pGraph->VexNum>20) { printf("\t\t\t警告：輸入數據錯誤！！！\n"); printf("\t\t\t按任意鍵回主菜單！！！"); getch(); returnFAILURE; } //初始化圖的弧數 printf("\t\t\t請輸入圖的弧度數(<=20)："); scanf("%d",&pGraph->ArcNum); //檢查 if(pGraph->ArcNum>20) { printf("\t\t\t警告：輸入數據錯誤！！！\n"); printf("\t\t\t按任意鍵回主菜單！！！"); getch(); returnFAILURE; } //初始化圖的頂點名稱 printf("\t\t\t---------------------------------\n"); printf("\t\t\t初始化的頂點名稱......\n"); for(inti=0;i<pGraph->VexNum;i++) { printf("\t\t\t請輸入第%d個頂點名稱：",i+1); scanf("%s",pGraph->Vexs[i]); } //初始化圖的弧權值為最大值 for(i=0;i<pGraph->VexNum;i++) for(intj=0;j<pGraph->VexNum;j++) pGraph->Arcs[i][j]=INF; //輸入弧的信息 printf("\t\t\t---------------------------------\n"); printf("\t\t\t初始化的弧的信息......\n"); printf("\t\t\t請輸入弧的信息(注：從0開始)：\n"); for(i=0;i<pGraph->ArcNum;i++) { intStav,Endv,Weight; printf("\t\t\t請輸入第%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創建景區景點分布圖成功！！！\n"); printf("\t\t\t按任意鍵回主菜單！！！"); getch(); returnSUCCESS;}輸出景區景點分布圖流程圖：程序：//輸出景區景點分布圖STATUSPrintGraph(constPGRAPHpGraph){ printf("\t\t\t_________________________________\n"); printf("\n\t\t\t$\t顯示景區景點分布圖\t$\n"); printf("\t\t\t_________________________________\n\n"); // printf("\t景區景點名稱......\n\t"); for(inti=0;i<pGraph->VexNum;i++) printf("%s\t",pGraph->Vexs[i]); printf("\n\n\t景區景點信息......\n"); 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"); else printf("%d\t",pGraph->Arcs[i][j]); printf("\n"); } printf("\t___________________________________________________________\n\t"); printf("按任意鍵回主菜單！！！"); getch(); returnSUCCESS;} 輸出景區導游線路圖圖的遍歷從圖中某一頂點出發訪遍圖中所有的頂點，且使每個頂點僅被訪問一次，這一過程就叫做圖的遍歷(TraversingGraph)。圖中也許存在回路，且圖的任一頂點都也許與其它頂點相通，在訪問完某個頂點之后也許會沿著某些邊又回到了曾經訪問過的頂點。為了避免反復訪問，可設立一個標志頂點是否被訪問過的輔助數組visited[]。輔助數組visited[]的初始狀態為0,在圖的遍歷過程中,一旦某一個頂點i被訪問,就立即讓visited[i]為1,防止它被多次訪問。兩種圖的遍歷方法:深度優先搜索DFS(DepthFirstSearch)廣度優先搜索BFS(BreadthFirstSearch)廣度優先搜索遍歷圖(BFS)對連通圖，從起始點V到其余各頂點必然存在途徑。其中，V->w1,V->w2,V->w8的途徑長度為1;V->w7,V->w3,V->w5的途徑長度為2;V->w6,V->w4的途徑長度為3從圖中的某個頂點V0出發，并在訪問此頂點之后依次訪問V0的所有未被訪問過的鄰接點，之后按這些頂點被訪問的先后順序依次訪問它們的鄰接點，直至圖中所有和V0有途徑相通的頂點都被訪問到。若此時圖中尚有頂點未被訪問,則另選圖中一個未曾被訪問的頂點作起始點，反復上述過程，直至圖中所有頂點都被訪問到為止。流程圖：程序：//輸出景區導游線路圖(注：廣度優先遍歷)STATUSTraverseGraph(constPGRAPHpGraph){ printf("\t\t\t_________________________________\n"); printf("\n\t\t\t$\t輸出景區導游線路圖\t$\n"); printf("\t\t\t_________________________________\n\n"); //定義訪問標志數組 bool*Visit=(bool*)malloc(pGraph->VexNum*sizeof(bool)); //初始化訪問標志數組為false for(inti=0;i<pGraph->VexNum;i++) Visit[i]=false; //定義隊列、并初始化隊列 QUEUEQueue; if(InitQueue(&Queue,pGraph->VexNum)==FAILURE) { printf("\t\t\t警告：創建隊列失敗！！！\n"); printf("\t\t\t按任意鍵回主菜單！！！"); getch(); returnFAILURE; } //定義訪問頂點變量，并初始值為0 intVertex=0; do { if(!Visit[Vertex]) { printf("\t\t\t%s景點......\n",pGraph->Vexs[Vertex]); //標志訪問過 Visit[Vertex]=true; //遍歷與Vertex相連的頂點并進隊 for(i=0;i<pGraph->VexNum;i++) if(Visit[i]==false&&pGraph->Arcs[Vertex][i]!=INF) EnQueue(&Queue,i); } //出隊 DeQueue(&Queue,&Vertex); }while(QueueLen(&Queue)); //銷毀隊列 DestroyQueue(&Queue); printf("\t\t\t按任意鍵回主菜單！！！"); getch(); returnSUCCESS;}有向圖的拓撲排序何謂“拓撲排序”？對有向圖進行如下操作:假設G=(V，E)是一個具有n個頂點的有向圖，V中頂點序列vl，v2，…，vn稱做一個拓撲序列(TopologicalOrder)，當且僅當該頂點序列滿足下列條件：若在有向圖G中存在從頂點vi到vj的一條途徑，則在頂點序列中頂點vi必須排在頂點vj之前。通常，在AOV網中，將所有活動排列成一個拓撲序列的過程叫做拓撲排序(TopologicalSort)。在AOV網中不應當出現有向環。由于環的存在意味著某項活動將以自己為先決條件，顯然無法形成拓撲序列。鑒定網中是否存在環的方法：對有向圖構造其頂點的拓撲有序序列，若網中所有頂點都出現在它的拓撲有序序列中，則該AOV網中一定不存在環。例如：對于有向圖可求得拓撲有序序列：ABCD或ACBDBBcDA cDA例如,對學生選課工程圖進行拓撲排序,得到的拓撲有序序列為C1,C2,C3,C4,C5,C6,C8,C9,C7或C1,C8,C9,C2,C5,C3,C4,C7,C6反之，對于下列有向圖不能求得它的拓撲有序序列。由于圖中存在一個回路{B,C,D}如何進行？輸入AOV網絡。令n為頂點個數。（1）在AOV網絡中選一個沒有直接前驅的頂點，并輸出之；（2）從圖中刪去該頂點,同時刪去所有它發出的有向邊；反復以上環節，直到所有頂點均已輸出，拓撲有序序列形成，拓撲排序完畢；或圖中尚有未輸出的頂點，但已跳出解決循環。這說明圖中還剩下一些頂點，它們都有直接前驅，再也找不到沒有前驅的頂點了。這時AOV網絡中必然存在有向環。在實現拓撲排序的算法中，采用鄰接表作為有向圖的存儲結構，每個頂點設立一個單鏈表，每個單鏈表有一個表頭結點，在表頭結點中增長一個存放頂點入度的域count，這些表頭結點構成一個數組。為了避免反復檢測入度為0的點，另設一棧存放所有入度為0的點。對于有n個頂點和e條邊的有向圖而言，for循環中建立入度為0的頂點棧時間為O（n）；若在拓撲排序過程中不出現有向環，則每個頂點出棧、入棧和入度減1的操作在while循環語句中均執行e次，因此拓撲排序總的時間花費為O(n+e)。流程圖:程序://有向圖的拓撲排序STATUSTopologicalSort(constPGRAPHpGraph){ printf("\t\t\t_________________________________\n"); printf("\n\t\t\t$\t導游線路圖有無回路\t$\n"); printf("\t\t\t_________________________________\n\n"); //定義入度數組,記錄每個頂點的入度，初始化為0 intIndegree[MAXNUM]={0}; //定義桟、并初始化桟 STACKStack; if(InitStack(&Stack,pGraph->VexNum)==FAILURE) { printf("\t\t\t警告：創建桟失敗！！！\n"); printf("\t\t\t按任意鍵回主菜單！！！"); getch(); returnFAILURE; } printf("\t\t\t計算各頂點的入度.....\n"); for(intj=0;j<pGraph->VexNum;j++) { //求各個頂點的入度 for(inti=0;i<pGraph->VexNum;i++) if(pGraph->Arcs[i][j]!=INF) Indegree[j]++; //入度為0的頂點入棧 if(!Indegree[j]) PushStack(&Stack,j); } printf("\t\t\t進行拓撲排序.....\n"); //Count用來指示入度為0的頂點個數 intCount=0,k; while(StackLen(&Stack)) { //出桟、并訪問 PopStack(&Stack,&k); printf("%s\t",pGraph->Vexs[k]); Count++; //對出棧的頂點所指向的頂點減一，并且將入度為0的頂點入棧 for(inti=0;i<pGraph->VexNum;i++) if(pGraph->Arcs[k][i]!=INF) if(!(--Indegree[i])) PushStack(&Stack,i); } //銷毀桟 DestroyStack(&Stack); //判斷是否是拓撲排序 if(Count<pGraph->VexNum) printf("\t\t\t結果：導游線路圖有回路\n"); else printf("\t\t\t結果：導游線路圖無回路\n"); printf("\t\t\t按任意鍵回主菜單！！！"); getch(); returnSUCCESS;}求兩個景點間的最短途徑最短途徑定義

所謂最短途徑問題是指：假如從圖中某一頂點（源點）到達另一頂點（終點）的途徑也許不止一條，如何找到一條途徑似的沿此途徑上各邊的權值總和（稱為途徑長度）達成最小。迪杰斯特拉(Dijkstra)算法求單源最短途徑

由Dijkstra提出的一種按途徑長度遞增序產生各頂點最短途徑的算法。

（1）按途徑長度遞增序產生各頂點最短途徑

若按長度遞增的順序生成從源點s到其它頂點的最短途徑，則當前正在生成的最短途徑上除終點以外，其余頂點的最短途徑均已生成（將源點的最短途徑看作是已生成的源點到其自身的長度為0的途徑）。（2）具體做法

一開始第一組只涉及頂點v1，第二組涉及其他所有頂點，v1相應的距離值為0，第二組的頂點相應的距離值是這樣擬定的：若圖中有邊<v1,vj>,則vj的距離為此邊所帶的權值，否則vj的距離值為一個很大的數(大于所有頂點間的途徑長度)，然后每次從第二組的頂點中選一個其距離值為最小的vm加入到第一組中。每往第一組加入一個頂點vm，就要對第二組的各個頂點的距離值進行一次修正。若加進vm做中間頂點，使從v1到vj的最短途徑比不加vm的途徑為短，則要修改vj的距離值。修改后再選距離最小的頂點加入到第一組中。如此進行下去，直到圖中所有頂點都涉及在第一組中，或再也沒有可加入到第一組中的頂點存在為止。

假設有向圖G的n個頂點為1到n,并用鄰接矩陣cost表達,若<vi,vj>是圖G中的邊，則cost[i][j]的值等于邊所帶的權;若<vi,vj>不是圖G中的邊，則cost[i][j]等于一個很大的數；若i=j,則cost[i][j]=0。此外,設立三個數組S[n]、dist[n]、pre[n]。S用以標記那些已經找到最短途徑的頂點，若S[i-1]=1,則表達已經找到源點到頂點i的最短途徑,若S[i-1]=0,則表達從源點到頂點i的最短途徑尚未求得。dist[i-1]用來記錄源點到頂點i的最短途徑。pre[i-1]表達從源點到頂點i的最短途徑上該點的前趨頂點，若從源點到該頂點無途徑，則用0作為其前一個頂點序號。流程圖:程序://求兩個景點間的最短途徑STATUSMinShortPath(constPGRAPHpGraph){ printf("\t\t\t_________________________________\n"); printf("\n\t\t\t$\t景點之間的最短途徑\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; } //定義起點、終點 intStav=-1,Endv=-1; //定義起點、終點名稱 charStaNam[MAXNUM],EndNam[MAXNUM]; printf("\t\t\t輸入起始點和終點名稱(格式：StaEnd)："); scanf("%s%s",StaNam,EndNam); for(i=0;i<pGraph->VexNum;i++) { if(!strcmp(pGraph->Vexs[i],StaNam)) //起始點名稱下標 Stav=i; if(!strcmp(pGraph->Vexs[i],EndNam)) //終點名稱下標 Endv=i; } //判斷起始點名稱和終點名稱是否存在 if(Stav==-1||Endv==-1) returnFAILURE; //定義桟、并初始化 STACKStack; if(InitStack(&Stack,pGraph->VexNum)==FAILURE) { printf("\t\t\t警告：創建桟失敗！！！\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("終點"); //銷毀桟 DestroyStack(&Stack); printf("\n\t\t\t按任意鍵回主菜單！！！"); getch(); returnSUCCESS;}輸出道路修建規劃圖prim算法在無向加權圖中，n個頂點的最小生成樹有n-1條邊，這些邊使得n個頂點之間可達，且總的代價最小。

prim算法是一種貪心算法，將所有的頂點劃分為2個集合，每次總在2個集合之間中找最小的一條邊，局部最優最終達成全局最優，這正是貪心的思想。

具體的描述參見相關書籍：

描述

從單一頂點開始，普里姆算法按照以下環節逐步擴大樹中所含頂點的數目，直到遍及連通圖的所有頂點。

1.輸入：一個加權連通圖，其中頂點集合為V，邊集合為E；

2.初始化：Vnew={x}，其中x為集合V中的任一節點（起始點），Enew={}；

3.反復下列操作，直到Vnew=V：

1.在集合E中選取權值最小的邊（u,v），其中u為集合Vnew中的元素，而v則不是（假如存在有多條滿足前述條件即具有相同權值的邊，則可任意選取其中之一）；

2.將v加入集合Vnew中，將（u,v）加入集合Enew中；

4.輸出：使用集合Vnew和Enew來描述所得到的最小生成樹。例如:流程圖:程序://輸出道路修建規劃圖(注：最小生成樹)STATUSMininumCST(constPGRAPHpGraph){ printf("\t\t\t_________________________________\n"); printf("\n\t\t\t$\t輸出道路修建規劃圖\t$\n"); printf("\t\t\t_________________________________\n\n"); //定義輔助數組變量 CLOSEDGEClosedge; intMin=0; //初始化輔助數組,從第一個頂點開始 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個點 for(i=1;i<pGraph->VexNum;i++) { //保存輔助數組中Closedge.Lowcost權值最小值 //查找第一個權值不是0的位置 for(intj=0;j<pGraph->VexNum;j++) if(Closedge.Lowcost[j]!=0) break; Min=j; //查找輔助數組中最小值 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; //選擇最小邊 for(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]); } } printf("\n\t\t\t按任意鍵回主菜單！！！"); getch(); returnSUCCESS;}1.3項目編碼實現#include<stdio.h>#include<stdlib.h>#include"Graph.h"intFrame(){ printf("\t\t\t_________________________________\n"); printf("\n\t\t\t$\t景區旅游信息管理系統\t$\n"); printf("\t\t\t_________________________________\n\n"); printf("\t\t\t1.創建景區景點分布圖\n\n"); printf("\t\t\t2.保存景區景點分布圖\n\n"); printf("\t\t\t3.讀取景區景點分布圖\n\n"); printf("\t\t\t4.輸出景區景點分布圖\n\n"); printf("\t\t