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

2021 iThome 鐵人賽

DAY 29

自我挑戰組

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

13th鐵人賽自學筆記 algorithm

吳他，惟手熟爾

2021-10-10 22:07:11

3322 瀏覽

分享至

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的虛擬碼，輸入一張圖 $G=(V,E)$ ，可以是有向圖，也可以是無向圖。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迴圈，都需要跑 $|V|$ 次，需要的時間為 $\Theta(V)$ ，而對於每一個位於集合 $V$ 中的節點，DFS-VISIT只會被呼叫一次，原因在於要成功呼叫DFS-VISIT的條件是該節點是白色的，而只要成功呼叫到DFS-VISIT，該節點就會變成灰色的，而因此不會被二次呼叫。

在DFS-VISIT中，for迴圈的迭代次數取決於u節點關連到的鄰接串列的長度，也就是 $|Adj[u]|$ 。而無論我們給定的是有向圖，還是無向圖，他們邊的數量皆為 $\Theta(E)$ ，因此在DFS-VISIT中，需要的時間為 $\Theta(E)$ ，因此，整體時間需要 $\Theta(V + E)$ 。

邊的分類(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連接了兩棵子樹。

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

節點為白色，表示 $(u,v)$ 為Tree edge
節點為灰色，表示 $(u,v)$ 為Back edge
節點為黑色，表示 $(u,v)$ 為Forward edge或是Cross edge

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

說明:

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

如果上面這是一張無向圖，則A走到B，B走到C，C是可以走到A的，因為沒有方向限制，所以會變成往回走，就無法形成Forward edge了，而是變成Backward edge。
不存在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 $\Longleftrightarrow$ 那麼就表示圖中有環產生，在有向圖和無向圖皆是如此，以下證明有向圖的兩種情況

證明只要有Back edge $\leftarrow$ 就有環產生

這張圖就是一個環，D是E的父親，A是E的祖父，存在Back edge。
證明只要有Back edge $\rightarrow$ 就有環產生

這個情況比較麻煩，我們必須先做出一些假設:
假設 $V_0$ 是第一個被DFS發現的節點，也就是第一個變成灰色的，我們要證明的是 $(V_k,V_0)$ 會是Back edge。

我們知道 $V_1$ 會在 $V_0$ 之前完成DFS遞迴走訪，也就是 $V_1$ 會在 $V_0$ 之前變成黑色，最先變成灰色的點，會最晚變成黑色，也就是Stack的概念，本質上是遞迴呼叫，我們可以拓展這個概念，通過歸納法，可以得知 $V_i$ 會比 $V_{i-1}$ 還要早變成黑色，再拓展，可以知道 $V_k$ 會在 $V_0$ 之前變成黑色，那麼我們就找到 $(V_k,V_0)$ 為Back edge了，遞迴過程看起來大致上如下。

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

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