基于隊列的廣度優(yōu)先遍歷算法設計與實現(xiàn)
2014-04-29 00:00:00王鵬程李光杰
計算機光盤軟件與應用 2014年2期
摘 要：本文主要介紹在二維數(shù)組鄰接矩陣存儲結(jié)構下下利用隊列對無向連通稠密圖進行廣度優(yōu)先遍歷的算法設計及實現(xiàn)過程，文中給出了算法思想，算法設計思路及具體實現(xiàn)代碼。
關鍵詞：廣度優(yōu)先；隊列；遍歷；鄰接矩陣
中圖分類號：TP311.12
圖是一種重要的非線性數(shù)據(jù)結(jié)構，在計算機中的物理存儲方式主要有鄰接矩陣和鄰接表兩種，其中鄰接矩陣適用于稠密圖，鄰接表適用于稀疏圖。對圖進行遍歷是依次訪問圖中所有頂點和邊的一種系統(tǒng)方法，即對非線性結(jié)構進行線性化的過程，圖的遍歷算法主要有廣度優(yōu)先、廣度優(yōu)先和最佳優(yōu)先3種，本文僅以圖1所示的無向連通稠密圖為例，采用圖2所示的二維數(shù)組鄰接矩陣作為存儲結(jié)構，介紹廣度優(yōu)先遍歷算法的設計和實現(xiàn)方法。
圖1 無向聯(lián)通圖
圖2 圖的鄰接矩陣存儲示意圖
1 廣度優(yōu)先遍歷思想
廣度優(yōu)先遍歷將圖中頂點分成若干層次，以圓環(huán)形式進行分層訪問。遍歷過程為：
（1）從圖中任一頂點v開始，當頂點v未被訪問過時，作訪問標記；
（2）遍歷v所有未被訪問的鄰接點v1，v2，……vk，作訪問標記；
（3）依次訪問v1，v2，……vk未被訪問的鄰接點，作訪問標記；繼續(xù)依次訪問各鄰接點未被訪問的鄰接點，直到?jīng)]有未被訪問的鄰接點為止。
2 廣度優(yōu)先的遍歷算法
本文的廣度優(yōu)先遍歷算法借助隊列實現(xiàn)，算法設計基本思路如下：
（1）初始化隊列；
（2）對所有節(jié)點作未訪問標記；
（3）起始節(jié)點入隊列；
（4）當隊列不為空時：
1）隊首頂點v出隊；
2）如果頂點v未標記為已訪問，則：
①打印v；
②標記v為已訪問；
③遍歷頂點v的鄰接點，如果鄰接點u未被標記為已訪問，則u入隊列。
對于一個含有V個頂點的無向連通圖，廣度優(yōu)先遍歷的非遞歸算法在最好的情況下（每個頂點僅有兩條邊相連）每個頂點僅被訪問一次，時間復雜度為O（n）；而在最壞的情況下（圖為完全圖時），搜索第i層結(jié)點時將會有n-i個結(jié)點入隊列，最多在隊列中存儲（n-2）*（n-1）/2個結(jié)點，此時的時間復雜度與遞歸算法類似，為O（n2）。
基于隊列的廣度優(yōu)先遍歷算法具體程序代碼如下：
private void BFVisit（int prev， int v）{
Queue q=new Queue（）；//建立存儲隊列
id = 0；
for（int i=1；i<=V；i++）
visited[i] = 0；//對所有頂點作未訪問標記
q.enqueue（v）；//頂點v入隊
Console.WriteLine（\"BF search by queue：\"）；
while （！q.isEmpty（））{//設置循環(huán)結(jié)束條件為隊列空
v =q.deQueue（）；//隊首元素v出隊
Console.WriteLine（\"{0}-\"，v）；
if （！visited[v]）{//如果頂點v未被訪問過
visited[v]=++id；//設置頂點v的訪問標記
for（int u=1；u<=V；u++）{//對頂點v所有未被訪問的鄰接點執(zhí)行入隊操作 if （visited[u]==0adj[v，u]！=0）
q.enQueue（u）；
}
}
}
}
利用廣度優(yōu)先遍歷的非遞歸算法BFVisit（）對圖1進行遍歷時，頂點的遍歷過程及相應隊列狀態(tài)如圖3所示。圖3中，新入隊的鄰接點用深色背景表示，如當遍歷頂點A的鄰接點時，B、C、D、G頂點先后入隊。
圖3 遍歷過程及隊列狀態(tài)
3 結(jié)束語
我們可以以任意順序訪問當前頂點的鄰接點，因此圖的廣度優(yōu)先遍歷結(jié)果不唯一。但在具體的算法設計和實現(xiàn)過程中，我們需要應用某種具體存儲結(jié)構來存儲和表示圖，進而設定特定的訪問規(guī)則進行遍歷，從而得到唯一的遍歷結(jié)果，如本文我們利用DFVisit（）算法對圖1進行廣度優(yōu)先遍歷時，遍歷的結(jié)果始終是A-B-C-D-G-E-H-F。
參考文獻：
[1]胡佳，趙福生.廣度優(yōu)先搜索在迷宮問題中的應用[J].江西教育學院學報，2013（02）.
[2]杜恒.圖的廣度優(yōu)先遍歷的算法實現(xiàn)[J].南陽師范學院學報，2012（12）.
[3]歐陽圣，胡望宇.幾種經(jīng)典搜索算法研究與應用[J].計算機系統(tǒng)應用，2011（05）.
[4]嚴蔚敏.數(shù)據(jù)結(jié)構[M].北京：清華大學出版社，1997.
[5]Michael T GoodRich， Data Structures Algorithms in C++，John Wiley Sons，Inc.
作者簡介：王鵬程（1992.05-），男，北京人，計算機專業(yè)，本科；李光杰（1980.09-），女，遼寧朝陽人，副教授，碩士，研究方向：軟件工程。
作者單位：北京工業(yè)大學耿丹學院信息工程系，北京 101301
