iT邦幫忙

2021 iThome 鐵人賽

DAY 28
0
自我挑戰組

從0開始啃Introduction of algorithms心得與記錄系列 第 28

Day-28 Breadth-First Search(BFS), 廣度優先搜尋

BFS簡介

BFS是用來遍歷一張圖的最簡單演算法,也是很多在圖論演算法的原型,許多演算法都是基於BFS,像是Prim最小生成樹,Dijkstra演算法等等。

給定一張圖https://chart.googleapis.com/chart?cht=tx&chl=G%3D(V%2CE),和一個節點s,BFS可以走訪s能夠到達的所有節點v,並且能夠紀錄s到各個節點的最少邊數,也就是最短距離,同時會產生出一棵BST Tree。這個數會以s作為樹的根結點,並且包含s能夠到達的所有節點v。BST可以用在有向圖,也可以用在無向圖中。

為了方面演示這個演算法,我們將結點以三個顏色做為表示,白色,灰色,黑色做為表示。所有節點在一開始的時候都標記為白色,在BST持續進行的過程,這些節點會變成灰色或是黑色。在遍歷的過程中,第一次遇到的節點就稱為該節點被發現,並且同時節點的顏色發生改變,黑色和灰色皆為已經被發現的節點。

白色表示還沒被其他節點發現的節點,灰色表示被其他節點發現的節點,且被推入Queue中,黑色表示被其他節點發現得節點,且已經被Pop出Queue。

下面為BFS的虛擬碼,假設給定圖https://chart.googleapis.com/chart?cht=tx&chl=G%3D(V%2CE),以鄰接矩陣表示,每一個節點作為物件表示,節點的顏色儲存在https://chart.googleapis.com/chart?cht=tx&chl=u.color中,https://chart.googleapis.com/chart?cht=tx&chl=u.%5Cpi儲存前驅節點,如果不存在節點,則表示為NULL,https://chart.googleapis.com/chart?cht=tx&chl=u.d紀錄s到u的距離。這個演算法還需要一個Queue來儲存灰色的節點。

BFS(G, s)
for each vertex u ∈ G.V - {s}
  u.color = WHITE
  u.d = ∞
  u.π = NULL
s.color = GRAY
s.d = 0
s.π = NULL
Q = ∅
ENQUEUE(Q, s)
while Q != ∅
u = DEQUEUE(Q)
for each v ∈ G.Adj[u]
  if v.color == WHITE
     v.color = GRAY
     v.d = u.d + 1
     v.π = u
     ENQUEUE(Q, v)
u.color = BLACK

  • (a)一開始從s節點開始,s節點被發現,標記為灰色,同時推入Queue中。
  • (b)將s彈出Queue,彈出的節點可以看做是目前所在節點,並將s標記為黑色,接著w, r被發現,標記成灰色,同時推入Queue中。1表示s一步就能到達的節點,儲存到v.d中。
  • (c)將w彈出Queue,並將w標記成黑色,可以將黑色視為目前所在的節點,接著,t和x被發現,標記成灰色,同時推入Queue。2表示s走兩步可以到的節點,步數儲存到v.d中。
  • (d)將r彈出Queue,並將r標記成黑色,r所在的地方發現到節點v,標記成灰色,並推入Queue,v是s兩步可以走到的節點,步數儲存到v.d中。
  • (e)將t彈出Queue,並將t標記成黑色,t所在的地方發現到節點u,標記成灰色,並推入Queue,u是s走三步可以走到的節點,步數儲存到v.d中。
  • (f)將x彈出Queue,並將x標記成黑色,x所在的地方發現到節點y,標記成灰色,並推入Queue,y是s走三步可以走到的節點,步數儲存到v.d中。
  • (g)將v彈出Queue,並將v標記成黑色,v所在的地方發現不到任何節點。
  • (h)將u彈出Queue,並將u標記成黑色,u所在的地方發現到y,但y已經在Queue中,故沒有新的節點被推入Queue。
  • (i)將y彈出Queue,並將y標記成黑色,y所在的地方發現不到任何節點。

在BFS中,一開始構建出的BFS Tree只會有一個根結點s,在遍歷過程中看到u節點的鄰接串列時,每當發現到一個白色節點v,就將結點v和https://chart.googleapis.com/chart?cht=tx&chl=(u%2Cv)邊加入到樹中。BFS Tree中,稱u節點是v節點的前驅點或是父節點。

在虛擬碼1到4行中,我們先將s節點從G.V集合中移出,並遍歷除了s的所有節點,都將他標記成白色,並將每一個節點的u.d標記成無限,無限的概念就是走不到的意思,引申為還沒走到的節點,並將每一個父節點標記成NULL。

在第5行將s標記成灰色,因為在BST最一開始時,我們便發現到s了,並且只有s是沒有被標記成白色的,第6行和第7行初始化s。第8,9行初始化Queue,Queue的初始狀態下,裡面只有s。

第10行到18行while迴圈一直執行到沒有灰色節點為止,在第一次迭代,只有s節點是灰色的,Queue中也是只有s節點,直到第11行Pop出來。

第12行到17行for迴圈對u節點的鄰接串列中每一個節點v進行探測,如果v為白色,表示還沒被發現,使用第14行到17行來發現節點,將剛剛白色的v節點塗上灰色,並將v.d = u.d + 1,改變距離,並將u當作是v的父節點,然後插入到Queue的尾端。

在第18行,檢查u的鄰接串列中所有節點後,將u節點標記成黑色。


以樹的形式來看BFS,就可以發現到廣度優先的特性了,我們可以觀察到我們是一層接著一層的去遍歷整棵樹,而這個特性可以給予我們到某一個節點的最短路徑,BFS好處在於可以告訴我們哪一些節點是s抵達不了的。

效率

從上面的例子觀察到,每一個節點最多就是出隊和入隊各一次,而Queue的入隊和出隊操作皆為https://chart.googleapis.com/chart?cht=tx&chl=O(1),總共在集合G.V中有|V|個節點,因此時間複雜度為https://chart.googleapis.com/chart?cht=tx&chl=O(V)。BFS只有在節點出隊的時候才會對節點對應到的鄰接串列進行遍歷,而無論是有向圖,還是無向圖,他們的鄰接串列的長度皆為https://chart.googleapis.com/chart?cht=tx&chl=%5CTheta(E),而整體BFS所需要的時間複雜度為https://chart.googleapis.com/chart?cht=tx&chl=O(V)%20%2B%20O(E)%20%3D%20O(V%20%2B%20E),而這是一個線性函數。

最短路徑

BFS可以找到從s節點到u節點之最短距離,我們定義從源節點s到v之間的最短距離$\delta(s,v)$之間所有路徑中具有最少邊數的路徑,如果u節點是s不可抵達的,則距離為無限,也就是$\delta(s,v) = \infty$

參考資料:Introductio to algorithms 3rd, Wiki, 101北一女資訊集訓


上一篇
Day-27 圖論(Graph)基本概念
下一篇
Day-29 Depth-First-Search(DFS), 深度優先搜尋
系列文
從0開始啃Introduction of algorithms心得與記錄30

尚未有邦友留言

立即登入留言