要找出從source到每個可抵達的vertex的其中一種路徑。
不同的點為：
(1) BFS長出一棵樹，而DFS長出多棵樹（Forest）
(2) 會額外記錄timestamp：
該node一開開始被找到的時間（變成灰色）、
以及完成搜尋所有和該node相鄰的vertex的時間（變成黑色）。
(3) DFS並不是計算最短路徑（最少edges數量）。
 |
| Introduction to Algorithms |
使用的資料結構：
(1) color：記錄目前vertex的狀態
(a) WHITE: 還沒被discovered
(b) GRAY: 已經被discovered，但和該vertex相鄰的node還沒全部被discovered
(c) BLACK: 已經被discovered，且和該vertex相鄰的node都已經被discovered
(2) π：記錄parent是誰
(3) d：discover的時間（從WHITE->GRAY的時間）
(4) f：finish的時間（從GRAY->BLACK的時間）
 |
| Introduction to Algorithms Fig. 22.4 |
從其中一個node出發，
接著會一直往深處搜索尚未拜訪過的node，
直到無路可走、或與當前node相鄰的所有node都拜訪過時，
就會開始一步一步往回走，然後再檢查有沒有還沒拜訪的節點，
直到每個點都拜訪過為止。
以上圖為例，出發點是u，
接著開始不斷往下搜尋，拜訪過的節點就塗灰，
當到了x的時候，與x相鄰的節點已經都拜訪過了，
就把x塗黑，接著開始一個一個節點往回走。
往回走的過程，因為與y,v,u相鄰的節點都已經拜訪過，
因此依序把他們塗黑。
node中的數字代表timestamp「start/finish」，
也就是該node第一次拜訪的時間、結束搜尋的時間。
值得注意的一點是，
DFS會因為我們node選擇的順序，而得到不同的結果。
例如，以u為起點時，也可以選擇先走x，
因此順序就會變成：u->x->v->y。
雖然結果不同，但實際上是不會造成任何問題。
【Parenthesis Theorem】
DFS有括號性質，
若用（ 表示被找到的時間，用 ）表示結束搜尋的時間，
則DFS的結果會構成一組完整的括號結構。
（左括號和右括號不是互相包含、不然就是互相分離）
以上圖的結果而言，會得到以下的括號結構：
(u (v (y (x x) y) v) u) (w (z z) w)
【White-Path Theorem】
從括號性質中可以得知：
在G的depth-first forest裡，
v是u的子孫 <==> u.d < v.d < v.f < u.f
v是u的子孫 <==> 設定u.d的時候，u到v有一條白色的路徑
【Edges 種類】
1. tree edges
DFS裡面的邊，
也就是若v是經由搜索(u,v)發現的，
那(u,v)即是tree edge。
2. back edges
連接u到它祖先v的邊(u,v)叫做back edge。
self-loop也算是back edge的一種。
3. forward edges
連接u到它子孫v的non-tree edge(u,v)。
4. cross edges
所有其他的edge。
可以是連接同一棵depth-first tree的邊，
或是連接不同tree的邊。
當我們一開始搜尋某條edge(u,v)時，
由v的顏色就可以判斷該edge的種類了。
1. WHITE => tree edge
2. GRAY => back edge
3. BLACK => forward edge (若u.d < v.d)
=> cross edge (若u.d > v.d)
除此之外，我們可以得到一個輔助定理：
一個有向圖(directed graph)不會產生cycle，
也就是該圖為dag (directed acyclic graph)，
若且唯若DFS的結果沒有產生back edge。
沒有留言:
張貼留言