[輸入]
圖的頂點(diǎn)個(gè)數(shù)N,圖中頂點(diǎn)之間的關(guān)系及起點(diǎn)A和終點(diǎn)B
[輸出]
若A到B無(wú)路徑,則輸出“There is no path” 否則輸出A到B路徑上個(gè)頂點(diǎn)
[存儲(chǔ)結(jié)構(gòu)]
圖采用鄰接矩陣的方式存儲(chǔ)。
[算法的基本思想]
采用廣度優(yōu)先搜索的方法,從頂點(diǎn)A開始,依次訪問與A鄰接的頂點(diǎn)VA1,VA2,...,VAK, 訪問遍之后,若沒有訪問B,則繼續(xù)訪問與VA1鄰接的頂點(diǎn)VA11,VA12,...,VA1M,再訪問與VA2鄰接頂點(diǎn)...,如此下去,直至找到B,最先到達(dá)B點(diǎn)的路徑,一定是邊數(shù)最少的路徑。實(shí)現(xiàn)時(shí)采用隊(duì)列記錄被訪問過的頂點(diǎn)。每次訪問與隊(duì)頭頂點(diǎn)相鄰接的頂點(diǎn),然后將隊(duì)頭頂點(diǎn)從隊(duì)列中刪去。若隊(duì)空,則說明到不存在通路。在訪問頂點(diǎn)過程中,每次把當(dāng)前頂點(diǎn)的序號(hào)作為與其鄰接的未訪問的頂點(diǎn)的前驅(qū)頂點(diǎn)記錄下來,以便輸出時(shí)回溯。
#include<stdio.h>
int number //隊(duì)列類型
typedef struct{
int q[20]
標(biāo)簽:
輸入
上傳時(shí)間:
2015-11-16
上傳用戶:ma1301115706