Graph: Breadth-First Search(BFS，廣度優先搜尋)
文章推薦指數： 80 %
演算法
Togglenavigation
SecondRound
Archives
Tags
About
先備知識與注意事項
在BinaryTree:Traversal(尋訪)與BinaryTree:建立一棵BinaryTree兩篇文章裡，介紹了如何利用queue在BinaryTree中進行Level-OrderTraversal，其概念便是：各個node相對於root有其對應的level，按照level由小到大依序對node進行Visiting。
而level便代表了node與root之「距離」，以Graph的語言來說，「距離」便是path的length(長度)/distance(距離)。
如圖一：
Level=2：path(A-B)、path(A-C)之length為\(1\)。
Level=3：path(A-B-D)、path(A-B-E)、path(A-C-F)之length為\(2\)。
Level=4：path(A-B-E-G)、path(A-B-E-H)之length為\(3\)。
而Breadth-FirstSearch(BFS，廣度優先搜尋)便是廣義的Level-OrderTraversal，將使用情境從Tree推廣至Graph。
圖一。
溫馨小提醒：在解釋演算法時，可能會用到Graph中的專有名詞，如undirected、connectedcomponent、weight等等，若覺得這些名詞像被打了馬賽克糊糊的，可以先回到Graph:Intro(簡介)狠狠回憶一番。
目錄
Breadth-FirstSearch(BFS，廣度優先搜尋)
演算法
程式碼
討論
參考資料
BFS/DFS系列文章
Breadth-FirstSearch(BFS，廣度優先搜尋)
所以BFS()的功能有哪些呢？
考慮圖二(a)的Graph(沒有weight、是connected的undirectedgraph)：
圖二(a)。
若選定以vertex(A)作為起點，對圖二(a)的G進行BFS()，可以得到：
從vertex(A)抵達在Graph裡所有「與vertex(A)在同一個connectedcomponent裡」的vertex的最短距離(shortestpath)。
(由於圖二(a)的Graph是connectedundirectedgraph，所以從G中任何一點出發進行BFS()皆能抵達其餘所有vertex。
)
不僅僅能夠得到vertex(I)與vertex(A)的最短距離為\(3\)，還能夠指出一條可能的path，說明要如何從vertex(A)走到vertex(I)，例如path:A-C-F-I，或者path:A-C-G-I。
演算法
在正式開始之前，需要先準備四項武器：
queue：如同Level-OrderTraversal，BFS()將使用queue來確保「先被搜尋到的vertex，就先成為新的搜尋起點」。
colorarray：利用color標記哪些vertex已經被「找到」，哪些還沒有。
白色表示該vertex還沒有被找過；
灰色表示該vertex已經被某個vertex找過；
黑色表示該vertex已經從queue的隊伍中移除。
distancearray：記錄每一個vertex與起點vertex之距離。
predecessorarray：記錄某個vertex是被哪一個vertex找到的，如此便能回溯路徑。
BFS()的方法如下：
初始化(initialization)，如圖二(b)：
把所有vertex塗成白色，表示還沒有任何vertex被「找到」。
把所有vertex的distance設為無限大，表示從起點vertex走不到，或者還沒有走到。
把所有vertex的predecessor清除(或者設成NULL、-1，可以辨識出何者為「起點」即可)。
建立空的queue。
圖二(b)。
把起點vertex(A)推進queue，如圖二(c)：
將vertex(A)塗成灰色，表示vertex(A)在之後的BFS()過程中，將不可能再被其他vertex「找到」。
distance[A]設為\(0\)。
換句話說，distance為\(0\)的vertex就是在「一個connectedcomponent」上進行BFS()的起點。
predecessor[A]不更動。
若將predecessor初始化成\(-1\)，即表示，在BFS()結束後，predecessor仍為\(-1\)的vertex即為起點。
圖二(c)。
接著，以queue的front當作新的起點搜尋。
新的起點是vertex(A)，便檢查所有與vertex(A)相鄰的vertex(見圖二(a)的AdjacencyList)，修改其color、distance、predecessor。
如圖二(d)，vertex(B)、vertex(C)、vertex(D)與vertex(A)相鄰，如果vertex的顏色是白色，表示還沒有被其他vertex「找到」，便執行以下步驟：
將三個vertex的color塗成灰色。
將distance[B]、distance[C]、distance[D]設成distance[A]\(+1=1\)。
將predecessor[B]、predecessor[C]、predecessor[D]設成vertex(A)。
把三個vertex按照「找到」的順序，依序推進queue裡。
最後，把vertex(A)塗黑，移出queue。
經過以上步驟，vertex(B)、vertex(C)、vertex(D)便被vertex(A)「找到」，並把predecessor設成vertex(A)，所以回溯路徑時，任何經過vertex(B)的path，必定是由vertex(A)來。
同理，vertex(C)與vertex(D)也是。
而distance[B]是vertex(A)的distance[A]加一，如此一來，只要到達vertex(A)是經由最短路徑，那麼從vertex(A)走到vertex(B)的路徑，也會是最短路徑。
由於vertex(A)是起點，distance[A]\(=0\)，因此，distance[B]\(=1\)一定是從vertex(A)走到vertex(B)的最短距離。
由於推進queue的順序正好是vertex被「找到」的順序，因此，之後要取得queue的front作為新的起點做搜尋時，便能確保按照先前被「找到」的順序(如同Tree的Level-OrderTraversal)。
圖二(d)：以vertex(A)作為搜尋起點。
接著，繼續以queue的front當作新的起點搜尋。
新的起點是vertex(B)，檢查所有與其相鄰的vertex，共有vertex(A)與vertex(E)。
由於vertex(A)已經被「找到」過(顏色為灰色或黑色)，因此，vertex(B)只能找到vertex(E)，便進行以下步驟：
將vertex(E)的color塗成灰色。
將distance[E]設成distance[B]\(+1=2\)。
將predecessor[E]設成vertex(B)。
將vertex(E)推進queue。
最後，把vertex(B)塗黑，移出queue。
圖二(e)：以vertex(B)作為搜尋起點。
由於vertex(B)是第一個distance為\(1\)且被視為搜尋起點的vertex，這就表示，所有distance為\(0\)的vertex都已經
被當作搜尋起點。
搜尋過其相鄰之vertex。
被塗成黑色。
往後queue裡面只會出現distance\(\geq1\)的vertex。
接下來，繼續以queue的front，得到vertex(C)作為新的起點，檢查其相鄰的vertex的顏色，如果是灰色或黑色(vertex(A)與vertex(E)已經被「找到」)則忽略，若是白色(vertex(F)、vertex(G)、vertex(H))，見圖二(f)：
將color修改成灰色。
將distance修改成distance[C]\(+1\)。
將predecessor修改成vertex(C)。
將vertex按照被「找到」的順序，推進queue。
將vertex(C)塗黑，移出queue。
圖二(f)：以vertex(C)作為搜尋起點。
接著，從queue的front找到vertex(D)，可惜所有與vertex(D)相鄰的vertex(A)與vertex(H)不是灰色就是黑色，都已經被「找到」，見圖二(g)：
將vertex(D)塗黑，移出queue。
圖二(g)：以vertex(D)作為搜尋起點。
接著，重複上述之步驟，直到queue被清空，即結束BFS()搜尋，見圖二(h)-(l)。
圖二(h)：以vertex(E)作為搜尋起點。
圖二(i)：以vertex(F)作為搜尋起點，將vertex(I)推進queue。
圖二(j)：以vertex(G)作為搜尋起點。
圖二(k)：以vertex(H)作為搜尋起點。
圖二(l)：以vertex(I)作為搜尋起點。
當queue中的vertex都被移除(pop())，表示AdjacencyList中的所有vertex都被當作起點搜尋過其相鄰的vertex，此時BFS()便完成，得到以vertex(A)為起點，所有其餘vertex之相對應distance與predecessor，如圖二(m)。
圖二(m)：。
程式碼
(為了簡化程式，以下程式將使用int處理資料，把\(9\)個vertexcharA~I依序對應到int0~8)
範例程式碼包含兩個部分main()與classGraph。
在main()中，主要有兩件事：
建立如圖二(a)的AdjacencyList；
進行BFS()。
在classGraph中：
privatemember：
num_vertex：需要在定義Graph的object(物件)時，給定vertex的數目，以便建立AdjacencyList(或者AdjacencyMatrix)。
std::vector<:list>>AdjList：利用C++標準函式庫(STL)提供的container(容器):std::vector與std::list來實現。
這樣的寫法的優點是：不需要使用到newoperator，便能夠將記憶體控管交給STL，不需要自行處理deleteoperator，以避免記憶體遺漏(memoryleak)，詳細討論請參考CodeReview：DepthFirstSearchandBreadthFirstSearchinC++。
color、distance、predecessor：將在BFS()中使用，功能如上述。
publicmember：
Constructor:Graph(intnum_vertex)：在定義Graph的object(物件)時，需要知道vertex的數目，並在constructor中定義好AdjList。
AddEdgeList(intfrom,into)：功能便是在AdjList新增從from到to的edge。
BFS(intStart)：前面提到的Graph恰好是connectedundirectedgraph，因此只要一次BFS()就能走到Graph中的所有vertex。
然而，有些Graph並不是connectedgraph，無法以任意vertex作為起點走到其餘所有vertex(Graph中具有多個connectedcomponent)，因此，需要再多一個迴圈(以下是用forloop)確保Graph中的全部vertex都被「找到」。
//C++code
#include
#include
討論
由於BFS()是用AdjList來判斷edge的連結狀況，因此，BFS()對undirectedgraph或directedgraph皆適用。
若將predecessorarray中，所有vertex的「前後關係」以edge連結，可以得到PredecessorSubgraph。
以圖三(a)的subgraph為例，因為其connected與acyclic的性質，使得PredecessorSubgraph會是一棵以起點vertex為root的Tree，又稱為Breadth-FirstTree，而所有PredecessorSubgraph出現的edge稱為treeedge。
(若Graph本身是由多個(strongly)connectedcomponent，則有可能得到Breadth-FirstForest，詳見Graph:利用DFS和BFS尋找ConnectedComponent)
圖三(a)。
如圖三(a)的Breadth-FirstTree可能不止有一種可能，原因在於「建立AdjacencyList時的順序」，將會影響到BFS()中的forloop在「找到」vertex時的順序。
如圖三(b)，若更改圖二(a)之AdjList，把vertex(A)之Linkedlist中，vertex(B)與vertex(C)之順序對調，使得BFS()在搜尋vertex時，vertex(C)會比vertex(B)更早進入queue，也就更早成為搜尋的新起點，那麼最後得到的Breadth-FirstTree就會不同。
不過，雖然Breadth-FirstTree不一樣，但是每個vertex相對於起點vertex的distance保證相同。
圖三(b)。
本篇文章所提供的BFS()演算法，其color之灰色與黑色可以合併，換句話說，若只使用白色與黑色，同樣能完成BFS()。
不過在下一篇文章將介紹的DFS()演算法中，白色、灰色與黑色將分別具有不同功能。
以上便是Breadth-FirstSearch(BFS，廣度優先搜尋)之介紹。
下一篇將介紹另一種在Graph同樣常見的搜尋方法：Depth-FirstSearch(DFS，深度優先搜尋)。
參考資料：
IntroductiontoAlgorithms,Ch22
FundamentalsofDataStructuresinC++,Ch6
CodeReview：DepthFirstSearchandBreadthFirstSearchinC++
TheoryofProgramming：AdjacencyListusingC++STL
GeeksforGeeks：Detectcycleinanundirectedgraph
BFS/DFS系列文章
Graph:Breadth-FirstSearch(BFS，廣度優先搜尋)
Graph:Depth-FirstSearch(DFS，深度優先搜尋)
Graph:利用DFS和BFS尋找ConnectedComponent
Graph:利用DFS尋找StronglyConnectedComponent(SCC)
Graph:利用DFS尋找DAG的TopologicalSort(拓撲排序)
回到目錄：
目錄：演算法與資料結構
tags:C++,Graph,BFS,
延伸文章資訊
- 1演算法筆記之DFS與BFS - w3c菜鳥教程
演算法筆記之DFS與BFS,基本思想深度優先搜尋dfs depth first search 它從某個狀態開始，不斷的轉移狀態直到無法轉移狀態，然後回退到前一步的狀.
- 2實作Graph與DFS、BFS圖形走訪演算法 - 寫點科普
廣度優先走訪BFS (Breadth First Search) ... BFS 以某個頂點作為起始點，一開始拜訪該頂點、再接著拜訪該頂點的所有相鄰頂點，接下來再拜訪下一層的頂點， ...
- 3【筆記】BFS (Breadth First Search，廣度優先搜尋) - Yui ...
【筆記】BFS (Breadth First Search，廣度優先搜尋) · 每拜訪一個鄰居，就一併把可行「鄰居的鄰居」加入queue的尾端。距離要加上1。 · 拜訪過所有可通行的點 ...
- 4Graph: Breadth-First Search(BFS，廣度優先搜尋)
演算法
- 5广度优先搜索- 维基百科，自由的百科全书
广度优先搜索算法（英語：Breadth-First Search，縮寫為BFS），又譯作寬度優先搜索，或橫向優先搜索，是一種圖形搜索演算法。簡單的說，BFS是從根節點開始，沿着树的 ...
