最短路徑算法在校園導游系統(tǒng)中的應用

楊麗萍

摘 要： 用無向網(wǎng)表示學校的平面圖，設計了該平面圖的存儲結構，并應用最短路徑算法實現(xiàn)了查詢圖中各景點的相關信息，以及查詢圖中任意兩個景點間的最短路徑的功能；應用克魯斯卡爾算法構造該平面圖的最小生成樹，求出可以連通所有景點的最短路徑。該系統(tǒng)為新生熟悉校園環(huán)境提供了方便。

關鍵詞： 無向網(wǎng)； 存儲結構； 最短路徑； 最小生成樹； 鄰接矩陣

中圖分類號：TP312 文獻標志碼：A 文章編號：1006-8228（2014）02-31-02

0 引言

每年新生入學，來自全國各地的學生懷揣理想來到美麗的校園，然而大學校園占地龐大，景點復雜，讓很多新生一開始都很茫然，他們需要一個指導以便盡快熟悉學習和生活環(huán)境。因此，本文應用最短路徑算法和最小生成樹算法設計了一個校園導游系統(tǒng)，為新生提供方便。

1 校園景點平面圖表示方法

5 測試與分析

5.1 構造測試數(shù)據(jù)

6 結束語

本文將最短路徑算法和克魯斯卡爾算法應用于校園導游系統(tǒng)中，實現(xiàn)了查詢?nèi)我鈨蓚€景點間的最短路徑和找出可以連通所有景點的最短路徑，為新生熟悉校園環(huán)境提供了方便。

參考文獻：

[1] 耿國華.數(shù)據(jù)結構—C語言描述[M].高等教育出版社，2005.

[2] 左孝凌等編.離散數(shù)學[M].上海科技文獻出版社，1982.

[3] 譚浩強，張基溫.C語言程序設計教程[M].高等教育出版社，2006.

[4] 何欽銘，顏暉.C語言程序設計[M].高等教育出版社，2008.