摘 要：本文主要介紹在二維數(shù)組鄰接矩陣存儲結(jié)構(gòu)下下利用隊列對無向連通稠密圖進行廣度優(yōu)先遍歷的算法設(shè)計及實現(xiàn)過程，文中給出了算法思想，算法設(shè)計思路及具體實現(xiàn)代碼。

關(guān)鍵詞：廣度優(yōu)先；隊列；遍歷；鄰接矩陣

中圖分類號：TP311.12

圖是一種重要的非線性數(shù)據(jù)結(jié)構(gòu)，在計算機中的物理存儲方式主要有鄰接矩陣和鄰接表兩種，其中鄰接矩陣適用于稠密圖，鄰接表適用于稀疏圖。對圖進行遍歷是依次訪問圖中所有頂點和邊的一種系統(tǒng)方法，即對非線性結(jié)構(gòu)進行線性化的過程，圖的遍歷算法主要有廣度優(yōu)先、廣度優(yōu)先和最佳優(yōu)先3種，本文僅以圖1所示的無向連通稠密圖為例，采用圖2所示的二維數(shù)組鄰接矩陣作為存儲結(jié)構(gòu)，介紹廣度優(yōu)先遍歷算法的設(shè)計和實現(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)，算法設(shè)計基本思路如下：

（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（））{//設(shè)置循環(huán)結(jié)束條件為隊列空

v =q.deQueue（）；//隊首元素v出隊

Console.WriteLine（\"{0}-\"，v）；

if （！visited[v]）{//如果頂點v未被訪問過

visited[v]=++id；//設(shè)置頂點v的訪問標記

for（int u=1；u<=V；u++）{//對頂點v所有未被訪問的鄰接點執(zhí)行入隊操作 if （visited[u]==0adj[v，u]！=0）

q.enQueue（u）；

}

}

}

}

利用廣度優(yōu)先遍歷的非遞歸算法BFVisit（）對圖1進行遍歷時，頂點的遍歷過程及相應(yīng)隊列狀態(tài)如圖3所示。圖3中，新入隊的鄰接點用深色背景表示，如當遍歷頂點A的鄰接點時，B、C、D、G頂點先后入隊。

圖3 遍歷過程及隊列狀態(tài)

3 結(jié)束語

我們可以以任意順序訪問當前頂點的鄰接點，因此圖的廣度優(yōu)先遍歷結(jié)果不唯一。但在具體的算法設(shè)計和實現(xiàn)過程中，我們需要應(yīng)用某種具體存儲結(jié)構(gòu)來存儲和表示圖，進而設(shè)定特定的訪問規(guī)則進行遍歷，從而得到唯一的遍歷結(jié)果，如本文我們利用DFVisit（）算法對圖1進行廣度優(yōu)先遍歷時，遍歷的結(jié)果始終是A-B-C-D-G-E-H-F。

參考文獻：

[1]胡佳，趙福生.廣度優(yōu)先搜索在迷宮問題中的應(yīng)用[J].江西教育學院學報，2013（02）.

[2]杜恒.圖的廣度優(yōu)先遍歷的算法實現(xiàn)[J].南陽師范學院學報，2012（12）.

[3]歐陽圣，胡望宇.幾種經(jīng)典搜索算法研究與應(yīng)用[J].計算機系統(tǒng)應(yīng)用，2011（05）.

[4]嚴蔚敏.數(shù)據(jù)結(jié)構(gòu)[M].北京：清華大學出版社，1997.

[5]Michael T GoodRich， Data Structures Algorithms in C++，John Wiley Sons，Inc.

作者簡介：王鵬程（1992.05-），男，北京人，計算機專業(yè)，本科；李光杰（1980.09-），女，遼寧朝陽人，副教授，碩士，研究方向：軟件工程。

作者單位：北京工業(yè)大學耿丹學院信息工程系，北京 101301