景區旅游信息管理系統數據結構課外實踐報告小組人員時彬強12級物聯網工程潘理想12級物聯網工程凡正宇12級物聯網工程萬路12級物聯網工程問題簡述首先通過系統管理者輸入景區的信息，以確定是一個什么樣的景區分布情況，供游客利用管理系統清楚地了解到本景區的基本情況（如：景點的名稱，景點間的距離）。制訂旅游景點導游線路策略，首先通過遍歷景點，給出一個入口景點，建立一個導游線路圖，導游線路圖用有向圖表示。遍歷采用深度優先策略，這也比較符合游客心理。為了使導游線路圖能夠優化，可通過拓樸排序判斷圖中有無回路，若有回路，則打印輸出回路中的景點，供人工優化。在導游線路圖中，還為一些不愿按線路走的游客提供信息服務，比如從一個景點到另一個景點的最短路徑和最短距離。在本線路圖中將輸出任意景點間的最短路徑和最短距離。在景區建設中，道路建設是其中一個重要內容。道路建設首先要保證能連通所有景點，但又要花最小的代價，通過求最小生成樹來解決這個問題。本任務中假設修建道路的代價只與它的里程相關。任務功能模塊如下：1）創建景區景點分布圖

2）輸出景區景點分布圖（鄰接矩陣）3）輸出導游線路圖4）判斷導游線路圖有無回路

5）求兩個景點間的最短路徑和最短距離6）輸出道路修建規劃圖

小組人員任務分工時彬強：導游線路圖的創建，最短路徑與最短距離潘理想：景區分布圖的創建與輸出凡正宇：拓撲排序判斷導游線路圖是否有回路萬 路：道路修建規劃圖的創建與輸出

解決問題的具體函數1）創建景區景點分布圖//尋找要查找頂點位置

int

LocateVex(ALGraph

G,stringv);

//創建圖的鄰接表存儲

voidCreatGraph(ALGraph&G);

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

//輸出圖的鄰接矩陣

voidOutputGraph(ALGraphG);3）輸出導游線路圖voidDFS(ALGraph

G,intv);//遞歸遍歷voidDFSTraverse(ALGraphG);//圖的深度遍歷voidCreatTourSortGraph(ALGraph

G,ALGraph&G1);//創建導游線路圖4）判斷導游線路圖有無回路//計算每個頂點的入度，存儲在indegree數組中

voidFindInDegree(ALGraphG1,intindegree[]);//拓撲排序

int

TopoSort(ALGraphG1);5）求兩個景點間的最短路徑和最短距離//計算最短路徑

voidShortestPath(ALGraph

G,intpath[][MAX_VERTEX_NUM],doubleD[][MAX_VERTEX_NUM]);//輸出最短路徑

voidMiniDistanse(ALGraph

G,int

path[][MAX_VERTEX_NUM],doubleD[][MAX_VERTEX_NUM]);//輸出走的路線

voidOutPutShortestPath(ALGraph

G,int

path[][MAX_VERTEX_NUM],

int

i,intj）;6）輸出道路修建規劃圖//尋找還沒有納入最小生成樹中的邊的最小值

int

Mininum(ALGraph

G,Edgea);//求最小生成樹

voidMiniSpanTree(ALGraph

G,stringu);景區圖v1v7v6v3v5v8v4v2v1v4v2v5v8v1v4v2v7v6v3v5v8v1v4