iT邦幫忙

2021 iThome 鐵人賽

DAY 29
0
自我挑戰組

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

Day-29 Depth-First-Search(DFS), 深度優先搜尋

DFS介紹

與昨天BFS不同的地方在於,BFS是給定一個節點s,接著找到s可以到達的所有節點,而DFS是遍歷整張圖,如果我們給定特定的節點s,我們使用BFS可能無法遍歷整張圖。

DFS顧名思義,就是盡量的深入遍歷整張圖。找到一個節點v,遍歷所有v能夠到達的節點,一但v能夠到達的節點都已經被發現,則回朔到v的前驅節點,也就是v的父節點,接著以該節點作為出發的節點,繼續尋找能夠到達的節點,不斷重複這樣的過程,直到整張圖被遍歷。

和前面的BFS一樣,為了方便演示,使用三種顏色來標記節點,還沒被發現的節點塗上白色,節點被發現後塗成灰色,在該節點的鄰接串列被遍歷完成後塗成黑色。

DFS還會在每一個節點上做一個時間註記,每個節點v共有兩個時間註記,第一個時間註記v.d記錄節點v第一次被發現的時間,第二個時間註記v.f記錄v的鄰接串列被掃描完成的時間,也就是結點v被塗上黑色的時候。

下面為DFS的虛擬碼,輸入一張圖https://chart.googleapis.com/chart?cht=tx&chl=G%3D(V%2CE),可以是有向圖,也可以是無向圖。time是一個全域變數,用來計算時間註記。

DFS(G)
for each vertex u ∈ G.V
  u.color = WHITE
  u.π = NULL
time = 0
for each vertex u ∈ G.V
  if u.color == WHITE
    DFS-VISIT(G, u)
    
DFS-VISIT(G, u)
time = time + 1
u.d = time
u.color = GRAY
for each v ∈ G:Adj[u]
  if v.color == WHITE
    v.π = u
    DFS-VISIT(G, v)
u.color = BLACK
time = time + 1
u.f = time

在DFS執行過程中,第1到3行遍歷屬於G圖中V集合內的所有點u,將這些節點塗成白色,前驅節點設成NULL。

第5到7行一次對每一個節點進行檢查,如果發現到結點顏色為白色,那麼呼叫DFS-VISIT進行走訪。

呼叫DFS-VISIT時,會產生出以u作為根節點的樹,位於原本DFS Tree當中,也就是說,當我們完成整個DFS,會產生出一棵巨大的樹,每一個子節點都是一棵樹,就像是森林一般。當DFS回傳時,每個節點u都會被打上時間標記,被發現的時間儲存到u.d,u的鄰接串列被完成走訪的時間儲存到u.f。

在DFS-VISIT中,讓time這個計時器開始推進,並將u的顏色變成灰色的這個時間點儲存到u.d中,接著for迴圈對節點u對應到的鄰接串列中,每一個節點v進行檢查,當v為白色,則不斷的遞迴走訪,不斷深入整張圖,直到u對應到的鄰接串列都被走訪完畢,這時候將u標記為黑色,並將該時間點儲存到u.f中。


給定一張圖 虛線表示非DFS樹的邊,而是圖的邊

  • (a) 從u節點開始,每一個節點中的數字代表兩個時間註記。

  • (b) u節點遞迴走訪走到v節點,v節點塗上灰色,且標記父節點為u節點,並將變成灰色的時間點儲存到v.d。

  • (c) 接著v節點遞迴走訪到y節點,並將y變成灰色,y的父節點為v,同時將變成灰色的時間點儲存到y.d。

  • (d) 接著y遞迴走訪到x,x的父節點為y。

  • (e) 接著x開始遞迴走訪,發現y節點和u節點都已經走訪過,而這就表示x的鄰接串列中所有節點都已經被走訪。

  • (f) 當x的鄰接串列中所有節點都已經走訪完畢,將x塗成黑色,並記住塗成黑色的時間點,儲存到x.f。

  • (g) x節點開始回朔到父節點y,y的鄰接串列已經走訪完畢,將y塗成黑色,並記住塗成黑色的時間點,儲存到y.f。

  • (h) y節點開始回朔到父節點v,v的鄰接串列已經走訪完畢,將v塗成黑色,並記住塗成黑色的時間點,儲存到v.f中。

  • (i)(j) v節點回朔到u節點,u節點的鄰接串列已經走訪完畢,將u塗成黑色,並記錄塗成黑色的時間點,儲存到u.f中。


u點已經遍歷完成,接著從v點開始,v點的鄰接串列中所有節點皆已經走訪完畢,故不做任何動作,接著從y點開始走訪

  • (l) y節點遞迴走訪到w節點,w節點塗成灰色,w節點的父節點為y,同時將變成灰色的時間點儲存到w.f。
  • (m) w節點遞迴走訪到z節點,z節點塗成灰色,z節點的父節點為w,同時將變成灰色的時間點儲存到z.f。
  • (o) z節點發現所有節點都已經走訪完畢,表示z節點的鄰接串列中所有節點都已經走訪完畢,故將z節點變成黑色,並記錄下z節點變成黑色的時間點,儲存到z.f中。
  • (p) z節點回朔到父節點w,w節點發現所有節點都已經走訪完畢,表示w節點的鄰接串列都已經走訪完畢,故將w節點變成黑色,同時儲存w節點變成黑色的時間點,儲存到w.f中。
  • 接著每一個節點都發現與該節點關連的鄰接串列都已經走訪完畢,故DFS已經走訪整張圖,整個走訪結束。

DFS效率

在DFS函式中,有兩個for迴圈,都需要跑https://chart.googleapis.com/chart?cht=tx&chl=%7CV%7C次,需要的時間為https://chart.googleapis.com/chart?cht=tx&chl=%5CTheta(V),而對於每一個位於集合https://chart.googleapis.com/chart?cht=tx&chl=V中的節點,DFS-VISIT只會被呼叫一次,原因在於要成功呼叫DFS-VISIT的條件是該節點是白色的,而只要成功呼叫到DFS-VISIT,該節點就會變成灰色的,而因此不會被二次呼叫。

在DFS-VISIT中,for迴圈的迭代次數取決於u節點關連到的鄰接串列的長度,也就是https://chart.googleapis.com/chart?cht=tx&chl=%7CAdj%5Bu%5D%7C。而無論我們給定的是有向圖,還是無向圖,他們邊的數量皆為https://chart.googleapis.com/chart?cht=tx&chl=%5CTheta(E),因此在DFS-VISIT中,需要的時間為https://chart.googleapis.com/chart?cht=tx&chl=%5CTheta(E),因此,整體時間需要https://chart.googleapis.com/chart?cht=tx&chl=%5CTheta(V%20%2B%20E)

邊的分類(Edge classification)

在上面圖中,我們使用了F, B, C來區分一些邊,下面將說明這些邊的性質

  • Tree edge 若可以經由一條邊走訪到新的節點,則稱該邊為Tree edge,在上圖中,實心線皆是Tree edge,而那些虛線的部分,我們可以分為三個種類
    • Forward edge : 可以直接存取到子孫的邊,像是x為u的子孫,因此u和x之間的邊為Forward edge
    • Backward edge : 可以直接存取到祖父的邊,像是v為x的祖父,因此v和x之間的邊為Backward edge
    • Cross edge : 如果將圖表示成DFS Tree,可以發現Cross連接了兩棵子樹。

而節點的顏色,可以告訴我們一些邊的訊息

  • 節點為白色,表示https://chart.googleapis.com/chart?cht=tx&chl=(u%2Cv)為Tree edge
  • 節點為灰色,表示https://chart.googleapis.com/chart?cht=tx&chl=(u%2Cv)為Back edge
  • 節點為黑色,表示https://chart.googleapis.com/chart?cht=tx&chl=(u%2Cv)為Forward edge或是Cross edge

如果給定的圖是一張無向圖,則只會存在Tree edge和Backward edge

說明:

  1. 不存在Forward edge
    給定一張有向圖,A走訪到B,再走到C,C回朔到A(這個回朔是遞迴的關係導致,不是直接往回走),然後A走到C,在有向圖中,是可能存在的。

    如果上面這是一張無向圖,則A走到B,B走到C,C是可以走到A的,因為沒有方向限制,所以會變成往回走,就無法形成Forward edge了,而是變成Backward edge。
  2. 不存在Cross edge
    給定一張有向圖,A走訪到B,接著回朔到A,A是B的父節點,A接著走訪到C,A是C的父節點,C接著走訪到B,等於是從一個子樹,走到另外一個子樹,因此這是Cross edge

    但如果這是一張無向圖,則A走到B,B走到C,C走到A,A是B的父節點,B是C的父節點,就無法形成Cross edge,而是每一條邊都是Tree edge。

有了這一些邊的性質,我們可以應用在一些方面,像是偵測一個圖中是否有環產生。

環(Cycle)的偵測與DFS性質

只要有Back edge https://chart.googleapis.com/chart?cht=tx&chl=%5CLongleftrightarrow那麼就表示圖中有環產生,在有向圖和無向圖皆是如此,以下證明有向圖的兩種情況

  1. 證明只要有Back edge https://chart.googleapis.com/chart?cht=tx&chl=%5Cleftarrow 就有環產生

    這張圖就是一個環,D是E的父親,A是E的祖父,存在Back edge。
  2. 證明只要有Back edge https://chart.googleapis.com/chart?cht=tx&chl=%5Crightarrow 就有環產生

    這個情況比較麻煩,我們必須先做出一些假設:
    假設https://chart.googleapis.com/chart?cht=tx&chl=V_0是第一個被DFS發現的節點,也就是第一個變成灰色的,我們要證明的是https://chart.googleapis.com/chart?cht=tx&chl=(V_k%2CV_0)會是Back edge。

我們知道https://chart.googleapis.com/chart?cht=tx&chl=V_1會在https://chart.googleapis.com/chart?cht=tx&chl=V_0之前完成DFS遞迴走訪,也就是https://chart.googleapis.com/chart?cht=tx&chl=V_1會在https://chart.googleapis.com/chart?cht=tx&chl=V_0之前變成黑色,最先變成灰色的點,會最晚變成黑色,也就是Stack的概念,本質上是遞迴呼叫,我們可以拓展這個概念,通過歸納法,可以得知https://chart.googleapis.com/chart?cht=tx&chl=V_i會比https://chart.googleapis.com/chart?cht=tx&chl=V_%7Bi-1%7D還要早變成黑色,再拓展,可以知道https://chart.googleapis.com/chart?cht=tx&chl=V_k會在https://chart.googleapis.com/chart?cht=tx&chl=V_0之前變成黑色,那麼我們就找到https://chart.googleapis.com/chart?cht=tx&chl=(V_k%2CV_0)為Back edge了,遞迴過程看起來大致上如下。

我們會發現這是一個十分平衡的過程,如果將上面那張圖的DFS過程換一種形式表達

可以發現到這個有趣的性質,並且如果有兩個時間區間出現重疊,則表示較小區間的較大大區間的後代。

參考資料:Introduction to algorithms 3rd


上一篇
Day-28 Breadth-First Search(BFS), 廣度優先搜尋
下一篇
Day-30 完賽心得
系列文
從0開始啃Introduction of algorithms心得與記錄30

尚未有邦友留言

立即登入留言