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

楊麗萍

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

關(guān)鍵詞： 無(wú)向網(wǎng)； 存儲(chǔ)結(jié)構(gòu)； 最短路徑； 最小生成樹(shù)； 鄰接矩陣

中圖分類(lèi)號(hào)：TP312 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1006-8228（2014）02-31-02

0 引言

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

1 校園景點(diǎn)平面圖表示方法

5 測(cè)試與分析

5.1 構(gòu)造測(cè)試數(shù)據(jù)

6 結(jié)束語(yǔ)

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

參考文獻(xiàn)：

[1] 耿國(guó)華.數(shù)據(jù)結(jié)構(gòu)—C語(yǔ)言描述[M].高等教育出版社，2005.

[2] 左孝凌等編.離散數(shù)學(xué)[M].上?？萍嘉墨I(xiàn)出版社，1982.

[3] 譚浩強(qiáng)，張基溫.C語(yǔ)言程序設(shè)計(jì)教程[M].高等教育出版社，2006.

[4] 何欽銘，顏暉.C語(yǔ)言程序設(shè)計(jì)[M].高等教育出版社，2008.