景區(qū)旅游信息管理系統(tǒng)[知識材料]

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

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

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

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

5、XTYPE Vexs;/圖的頂點向量int LowcostMAXNUM;/*PCLOSEDGE;/定義輔助數(shù)組指針數(shù)據(jù)類型1.2.3項目模塊設計創(chuàng)建景區(qū)景點分布圖一. 鄰接矩陣 (Adjacency Matrix)(二維數(shù)組表示法）在圖的鄰接矩陣表示中，有一個記錄各個頂點信息的頂點表，還有一個表示各個頂點之間關系的鄰接矩陣。設圖 A = (V, E)是一個有 n 個頂點的圖, 圖的鄰接矩陣是一個二維數(shù)組 A.edgenn，定義(滿足如下條件的n階矩陣)：無向圖數(shù)組表示法特點：1）無向圖鄰接矩陣是對稱矩陣，同一條邊表示了兩次；2）頂點v的度：在無向圖中等于二維數(shù)組對應行（或列）中1的個數(shù)；在有向

6、圖中, 統(tǒng)計第 i 行 1 的個數(shù)可得頂點 i 的出度，統(tǒng)計第 j 列 1 的個數(shù)可得頂點 j 的入度。3）判斷兩頂點v、u是否為鄰接點：只需判二維數(shù)組對應分量是否為1；4）頂點不變，在圖中增加、刪除邊：只需對二維數(shù)組對應分量賦值1或清0；5）設存儲頂點的一維數(shù)組大小為n(圖的頂點數(shù)n), G占用存儲空間：n+n2；G占用存儲空間只與它的頂點數(shù)有關，與邊數(shù)無關；適用于邊稠密的圖；流程圖：程序：/創(chuàng)建景區(qū)景點分布圖STATUS CreateGraph(PGRAPH pGraph)printf(ttt_n);printf(nttt$t創(chuàng)建景區(qū)景點分布圖t$n);printf(ttt_n);/初始化

7、圖的頂點數(shù)printf(ttt初始化頂點數(shù)和弧度數(shù).n);printf(ttt請輸入圖的頂點數(shù)(VexNum);/檢查if(pGraph-VexNum20)printf(ttt警告：輸入數(shù)據(jù)錯誤！n);printf(ttt按任意鍵回主菜單！);getch();return FAILURE;/初始化圖的弧數(shù)printf(ttt請輸入圖的弧度數(shù)(ArcNum);/檢查if(pGraph-ArcNum20)printf(ttt警告：輸入數(shù)據(jù)錯誤！n);printf(ttt按任意鍵回主菜單！);getch();return FAILURE;/初始化圖的頂點名稱printf(ttt-n);printf(

8、ttt初始化的頂點名稱.n);for(int i=0;iVexNum;i+)printf(ttt請輸入第%d個頂點名稱：,i+1);scanf(%s,pGraph-Vexsi);/初始化圖的弧權值為最大值for(i=0;iVexNum;i+)for(int j=0;jVexNum;j+)pGraph-Arcsij=INF;/輸入弧的信息printf(ttt-n);printf(ttt初始化的弧的信息.n);printf(ttt請輸入弧的信息(注：從0開始)：n);for(i=0;iArcNum;i+)int Stav,Endv,Weight;printf(ttt請輸入第%d條弧(格式：Vi V

9、j Weight)：,i+1);scanf(%d%d%d,&Stav,&Endv,&Weight);pGraph-ArcsEndvStav=Weight;pGraph-ArcsStavEndv=Weight;printf(ttt創(chuàng)建景區(qū)景點分布圖成功！n);printf(ttt按任意鍵回主菜單！);getch();return SUCCESS;輸出景區(qū)景點分布圖流程圖：程序：/輸出景區(qū)景點分布圖STATUS PrintGraph(const PGRAPH pGraph)printf(ttt_n);printf(nttt$t顯示景區(qū)景點分布圖t$n);printf(ttt_nn);/printf

10、(t景區(qū)景點名稱.nt);for(int i=0;iVexNum;i+)printf(%st,pGraph-Vexsi);printf(nnt景區(qū)景點信息.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(按任意鍵回主菜單！);getch();return SUCCESS;輸出景區(qū)導游線路圖圖的遍歷從圖中某一頂點出發(fā)訪遍圖中所有的頂點，且使每個頂點僅

11、被訪問一次，這一過程就叫做圖的遍歷 (Traversing Graph)。圖中可能存在回路，且圖的任一頂點都可能與其它頂點相通，在訪問完某個頂點之后可能會沿著某些邊又回到了曾經訪問過的頂點。為了避免重復訪問，可設置一個標志頂點是否被訪問過的輔助數(shù)組 visited 。輔助數(shù)組 visited 的初始狀態(tài)為 0, 在圖的遍歷過程中, 一旦某一個頂點 i 被訪問, 就立即讓 visited i 為 1, 防止它被多次訪問。兩種圖的遍歷方法:深度優(yōu)先搜索 DFS (Depth First Search)廣度優(yōu)先搜索 BFS (Breadth First Search)廣度優(yōu)先搜索遍歷圖(BFS)對連

12、通圖，從起始點V到其余各頂點必定存在路徑。 其中，V-w1, V-w2, V-w8 的路徑長度為1; V-w7, V-w3, V-w5 的路徑長度為2; V-w6, V-w4 的路徑長度為3從圖中的某個頂點V0出發(fā)，并在訪問此頂點之后依次訪問V0的所有未被訪問過的鄰接點，之后按這些頂點被訪問的先后次序依次訪問它們的鄰接點，直至圖中所有和V0有路徑相通的頂點都被訪問到。 若此時圖中尚有頂點未被訪問,則另選圖中一個未曾被訪問的頂點作起始點，重復上述過程，直至圖中所有頂點都被訪問到為止。流程圖：程序： /輸出景區(qū)導游線路圖(注：廣度優(yōu)先遍歷)STATUS TraverseGraph(const PG

13、RAPH pGraph)printf(ttt_n);printf(nttt$t輸出景區(qū)導游線路圖t$n);printf(ttt_nn);/定義訪問標志數(shù)組bool* Visit=(bool*)malloc(pGraph-VexNum*sizeof(bool);/初始化訪問標志數(shù)組為falsefor(int i=0;iVexNum;i+)Visiti=false;/定義隊列、并初始化隊列QUEUE Queue;if(InitQueue(&Queue,pGraph-VexNum)=FAILURE)printf(ttt警告：創(chuàng)建隊列失敗！n);printf(ttt按任意鍵回主菜單！);getch()

14、;return FAILURE;/定義訪問頂點變量，并初始值為0int Vertex=0;doif(!VisitVertex)printf(ttt%s景點.n,pGraph-VexsVertex);/標志訪問過VisitVertex=true;/遍歷與Vertex相連的頂點并進隊for(i=0;iVexNum;i+)if(Visiti=false&pGraph-ArcsVertexi!=INF)EnQueue(&Queue,i);/出隊DeQueue(&Queue,&Vertex);while(QueueLen(&Queue);/銷毀隊列DestroyQueue(&Queue);printf(

15、ttt按任意鍵回主菜單！);getch();return SUCCESS;有向圖的拓撲排序何謂“拓撲排序”？ 對有向圖進行如下操作:假設G=(V，E)是一個具有n個頂點的有向圖，V中頂點序列vl，v2，vn稱做一個拓撲序列(Topological Order)，當且僅當該頂點序列滿足下列條件：若在有向圖G中存在從頂點vi到vj的一條路徑，則在頂點序列中頂點vi必須排在頂點vj之前。通常，在AOV網中，將所有活動排列成一個拓撲序列的過程叫做拓撲排序(Topological Sort)。在AOV網中不應該出現(xiàn)有向環(huán)。因為環(huán)的存在意味著某項活動將以自己為先決條件，顯然無法形成拓撲序列。判定網中是否存

16、在環(huán)的方法：對有向圖構造其頂點的拓撲有序序列，若網中所有頂點都出現(xiàn)在它的拓撲有序序列中，則該AOV網中一定不存在環(huán)。例如：對于有向圖 可求得拓撲有序序列： A B C D 或 A C B DBcDA例如, 對學生選課工程圖進行拓撲排序, 得到的拓撲有序序列為 C1 , C2 , C3 , C4 , C5 , C6 , C8 , C9 , C7或 C1 , C8 , C9 , C2 , C5 , C3 , C4 , C7 , C6 反之，對于下列有向圖 不能求得它的拓撲有序序列。 因為圖中存在一個回路 B, C, D 如何進行 ？輸入AOV網絡。令 n 為頂點個數(shù)。 （1）在AOV網絡中選一個沒

17、有直接前驅的頂點，并輸出之； （2）從圖中刪去該頂點, 同時刪去所有它發(fā)出的有向邊；重復以上步驟，直到全部頂點均已輸出，拓撲有序序列形成，拓撲排序完成；或圖中還有未輸出的頂點，但已跳出處理循環(huán)。這說明圖中還剩下一些頂點，它們都有直接前驅，再也找不到沒有前驅的頂點了。這時AOV網絡中必定存在有向環(huán)。在實現(xiàn)拓撲排序的算法中，采用鄰接表作為有向圖的存儲結構，每個頂點設置一個單鏈表，每個單鏈表有一個表頭結點，在表頭結點中增加一個存放頂點入度的域count，這些表頭結點構成一個數(shù)組。為了避免重復檢測入度為0的點，另設一棧存放所有入度為0的點。對于有n個頂點和e條邊的有向圖而言，for循環(huán)中建立入度為0的

18、頂點棧時間為O（n）；若在拓撲排序過程中不出現(xiàn)有向環(huán)，則每個頂點出棧、入棧和入度減1的操作在while循環(huán)語句中均執(zhí)行e次，因此拓撲排序總的時間花費為O (n+e)。流程圖:程序:/有向圖的拓撲排序STATUS TopologicalSort(const PGRAPH pGraph)printf(ttt_n);printf(nttt$t導游線路圖有無回路t$n);printf(ttt_nn);/定義入度數(shù)組,記錄每個頂點的入度，初始化為0int IndegreeMAXNUM=0;/定義桟、并初始化桟STACK Stack;if(InitStack(&Stack,pGraph-VexNum)=F

19、AILURE)printf(ttt警告：創(chuàng)建桟失?。);printf(ttt按任意鍵回主菜單！);getch();return FAILURE;printf(ttt計算各頂點的入度.n);for(int j=0;jVexNum;j+)/求各個頂點的入度for(int i=0;iVexNum;i+)if(pGraph-Arcsij!=INF)Indegreej+;/入度為0的頂點入棧 if(!Indegreej)PushStack(&Stack,j);printf(ttt進行拓撲排序.n);/Count用來指示入度為0的頂點個數(shù)int Count=0,k;while(StackLen(&Sta

20、ck)/出桟、并訪問PopStack(&Stack,&k);printf(%st,pGraph-Vexsk);Count+;/對出棧的頂點所指向的頂點減一 ，并且將入度為0的頂點入棧for(int i=0;iVexNum;i+)if(pGraph-Arcski!=INF)if(!(-Indegreei)PushStack(&Stack,i);/銷毀桟DestroyStack(&Stack);/判斷是否是拓撲排序if(CountVexNum)printf(ttt結果：導游線路圖有回路n);elseprintf(ttt結果：導游線路圖無回路n);printf(ttt按任意鍵回主菜單！);getch

21、();return SUCCESS;求兩個景點間的最短路徑最短路徑定義所謂最短路徑問題是指：如果從圖中某一頂點（源點）到達另一頂點（終點）的路徑可能不止一條，如何找到一條路徑似的沿此路徑上各邊的權值總和（稱為路徑長度）達到最小。迪杰斯特拉(Dijkstra)算法求單源最短路徑由Dijkstra提出的一種按路徑長度遞增序產生各頂點最短路徑的算法。（1）按路徑長度遞增序產生各頂點最短路徑若按長度遞增的次序生成從源點s到其它頂點的最短路徑，則當前正在生成的最短路徑上除終點以外，其余頂點的最短路徑均已生成（將源點的最短路徑看作是已生成的源點到其自身的長度為0的路徑）。（2）具體做法一開始第一組只包括頂

22、點 v 1 ，第二組包括其他所有頂點， v 1 對應的距離值為 0 ，第二組的頂點對應的距離值是這樣確定的：若圖中有邊 , 則 v j 的距離為此邊所帶的權值，否則 v j 的距離值為一個很大的數(shù) ( 大于所有頂點間的路徑長度 ) ，然后每次從第二組的頂點中選一個其距離值為最小的 v m 加入到第一組中。每往第一組加入一個頂點 v m ，就要對第二組的各個頂點的距離值進行一次修正。若加進 v m 做中間頂點，使從 v 1 到 v j 的最短路徑比不加 v m 的路徑為短，則要修改 v j 的距離值。修改后再選距離最小的頂點加入到第一組中。如此進行下去，直到圖中所有頂點都包括在第一組中，或再也沒

23、有可加入到第一組中的頂點存在為止。假設有向圖 G 的 n 個頂點為 1 到 n, 并用鄰接矩陣 cost 表示 , 若 是圖 G 中的邊，則 costij 的值等于邊所帶的權 ; 若 不是圖 G 中的邊，則 costij 等于一個很大的數(shù)；若 i=j, 則 costij=0 。另外 , 設置三個數(shù)組 Sn 、 distn 、 pren 。 S 用以標記那些已經找到最短路徑的頂點，若 Si-1=1, 則表示已經找到源點到頂點 i 的最短路徑 , 若 Si-1=0, 則表示從源點到頂點 i 的最短路徑尚未求得。 disti-1 用來記錄源點到頂點 i 的最短路徑。 prei-1 表示從源點到頂點

24、i 的最短路徑上該點的前趨頂點，若從源點到該頂點無路徑，則用 0 作為其前一個頂點序號。流程圖:程序:/求兩個景點間的最短路徑STATUS MinShortPath(const PGRAPH pGraph)printf(ttt_n);printf(nttt$t景點之間的最短路徑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;Path

25、Matrixij=-1;/求PathMatrix矩陣for(k=0;kVexNum;k+)for(i=0;iVexNum;i+)for(j=0;jVexNum;j+)if(DisMatrixijDisMatrixik+DisMatrixkj)DisMatrixij=DisMatrixik+DisMatrixkj;PathMatrixij=k;/定義起點、終點int Stav=-1,Endv=-1;/定義起點、終點名稱char StaNamMAXNUM,EndNamMAXNUM;printf(ttt輸入起始點和終點名稱(格式：Sta End)：);scanf(%s%s,StaNam,EndNam

26、);for(i=0;iVexNum;i+)if(!strcmp(pGraph-Vexsi,StaNam)/起始點名稱下標Stav=i;if(!strcmp(pGraph-Vexsi,EndNam)/終點名稱下標Endv=i;/判斷起始點名稱和終點名稱是否存在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

27、)PushStack(&Stack,Endv);Endv=PathMatrixStavEndv;/將所有路徑出桟、并輸出printf(ttt);while(1)printf(%s-,pGraph-VexsStav);if(!StackLen(&Stack)break;PopStack(&Stack,&Stav);printf(終點);/銷毀桟DestroyStack(&Stack);printf(nttt按任意鍵回主菜單！);getch();return SUCCESS;輸出道路修建規(guī)劃圖prim算法在無向加權圖中，n個頂點的最小生成樹有n-1條邊，這些邊使得n個頂點之間可達，且總的代價最小。

28、prim算法是一種貪心算法，將全部的頂點劃分為2個集合，每次總在2個集合之間中找最小的一條邊，局部最優(yōu)最終達到全局最優(yōu)，這正是貪心的思想。具體的描述參見相關書籍：描述從單一頂點開始，普里姆算法按照以下步驟逐步擴大樹中所含頂點的數(shù)目，直到遍及連通圖的所有頂點。1.輸入：一個加權連通圖，其中頂點集合為V，邊集合為E； 2.初始化：Vnew = x，其中x為集合V中的任一節(jié)點（起始點），Enew = ； 3.重復下列操作，直到Vnew = V： 1.在集合E中選取權值最小的邊（u, v），其中u為集合Vnew中的元素，而v則不是（如果存在有多條滿足前述條件即具有相同權值的邊，則可任意選取其中之一）；

29、 2.將v加入集合Vnew中，將（u, v）加入集合Enew中； 4.輸出：使用集合Vnew和Enew來描述所得到的最小生成樹。例如: 流程圖:程序:/輸出道路修建規(guī)劃圖(注：最小生成樹)STATUS MininumCST(const PGRAPH pGraph)printf(ttt_n);printf(nttt$t輸出道路修建規(guī)劃圖t$n);printf(ttt_nn);/定義輔助數(shù)組變量CLOSEDGE Closedge;int Min=0;/初始化輔助數(shù)組,從第一個頂點開始for(int i=1;iVexNum;i+)Closedge.Lowcosti=pGraph-ArcsMini;s

30、trcpy(Closedge.Vexsi,pGraph-VexsMin);Closedge.LowcostMin=0;/選這其余的pGraph-VexNum-1個點for(i=1;iVexNum;i+)/保存輔助數(shù)組中Closedge.Lowcost權值最小值/查找第一個權值不是0的位置for(int j=0;jVexNum;j+)if(Closedge.Lowcostj!=0)break;Min=j;/查找輔助數(shù)組中最小值for(j=0;jVexNum;j+)if(Closedge.Lowcostj&Closedge.Lowcostj%sn,Closedge.VexsMin,pGraph-V

31、exsMin);/Closedge.LowcostMin=0;/選擇最小邊f(xié)or(j=0;jVexNum;j+)if(pGraph-ArcsMinjArcsMinj;strcpy(Closedge.Vexsj,pGraph-VexsMin);printf(nttt按任意鍵回主菜單！);getch();return SUCCESS;1.3項目編碼實現(xiàn)#include #include #include Graph.hint Frame()printf(ttt_n);printf(nttt$t景區(qū)旅游信息管理系統(tǒng)t$n);printf(ttt_nn);printf(ttt1.創(chuàng)建景區(qū)景點分布圖nn);printf(ttt2.保存景區(qū)景點分布圖nn);printf(ttt3.讀取景區(qū)景點分布圖nn);printf(ttt4.輸出景區(qū)景點分布圖nn);printf(ttt5.輸出景區(qū)導游線路圖nn);printf(ttt6.導游線路圖有無回路nn);printf(ttt7.景點之間的最短路徑nn);printf(ttt8.輸出道路修建規(guī)劃圖nn);printf(ttt9.退出信息管理系統(tǒng)nn);printf(ttt請選擇相應功能：);return 0;int Menu