[Algorithm Cheat sheet] — Depth First Search and its Application

對於學習演算法來說，DFS Algorithm必定是其中的一塊大石頭。

1. DFS Algorithm [C.L.S]
2. Edge classfication
3. DFS — application algorithm.

DFS Algorithm [C.L.S]

以聖經本的解釋來說，一個Node(u) 記錄著4項欄位

1. color[u] : Node u 目前的狀態。可以為{WHITE(未被探索到)、GREY(正被探訪)、BLACK(已完成搜索)}
2. 𝛑[u] : 紀錄Node u的Parent，也是Node u第一次被探訪時的前一 個Node
3. d[u] :(discover time) Node u 第一次被發現的時間。
4. f[u] : (finish time ) Node u 結束的時間。

Example of GIF

Using FIFO queue(stack) to implement DFS

Edge Classfication

在DFS的traversal過程中，edge(u,v)的分類是取決於是否”先”拜訪過 v，然後再依照，v和u的關係來分類，詳細說明如下:

1.如果v在我們使用edge(u,v)拜訪時，是第一次被拜訪，則 edge(u,v) ∈ tree edge.
2.否則(表示v在之前已經被拜訪過):
   (a.)如果v是u的ancestor，則 edge(u, v)∈ back edge.
   (b.)否則，若v是u的descendant，則 edge(u, v)∈ forward edge.
   (c.)又否則，v不是u的descendant/ancestor，則edge(u, v)∈ cross edge.

利用上述邊的分類法，可以修改DFS-Visited的code :

根據color[u]和color[v] 來為edge分類:(u->v)

color classfication by DFS

1.若 color[v]="white"
(v尚未被拜訪過)
edge(u,v) ∈ tree edge.
2.若 color[v]="gray"
(v正在被拜訪)
edge(u,v) ∈ back edge.
3.若 "d[u]<d[v]"
(v為u的descendant)
edge(u,v) ∈ forward edge.
4.否則 :
(不為上述任何情況)
edge(u, v)∈ cross edge

Note :

當Graph為undirected graph時，因為forward edge可以視為back edge的反向，cross edge可以視為tree edge的反向。

因此，在Undirected Graph中僅有back edge及tree edge。

DFS — Application

1.) Detecting cycle in a graph

If “any back edge exist in graph “ then if and only if “G has cycle”

原因很簡單，若(u,v) 為back edge :

代表 u 為 v 在 DFS spanning tree 上的子孫 ， 因此必有一條path自 v 到 u 。 又(u,v)為一條自u到v的Path，因此v到v為一個cycle。

2.) Path Finding between u & v
我們可以稍微修改DFS algorithm 來判斷是否有一條path在頂點u和v之間

a.) 呼叫 DFS(u) ..使用u作為起點展開的dfs spanning tree .
b.) 使用"Stack"來追蹤目前的vertex與起點的path .
c.)只要一遇到 vertex v，馬上回傳目前的stack .

3.) Topological Sorting

Topological Sort 是一種linear ordering 的排序方法，使得在D.A.G中的每一個directed edge(u,v)， 頂點 u 一定比頂點 v 還要早發生 (拜訪順序).

#.Topological Sorting for a graph is not possible if the graph is not a DAG.

#.There can be more than one topological sorting for a graph .

而稍微的修改DFS能夠實現 Topological Sort :

In DFS, we start from a vertex, we first print it and then recursively call DFS for its adjacent vertices. In topological sorting, we use a temporary stack. We don’t print the vertex immediately, we first recursively call topological sorting for all its adjacent vertices, then push it to a stack. Finally, print contents of stack. Note that a vertex is pushed to stack only when all of its adjacent vertices (and their adjacent vertices and so on) are already in stack

Note :

至此，Detection Cycle 在 Diagraph 與 Undirected Graph，便各有其方法 :

i.) Undirected Graph : 如果存在back edge 則必有cycle。

ii.)Diagraph : ?

4.) To test if a graph is bipartite
我們可以在BFS/DFS 拜訪每個節點時，特別在新拜訪一個節點時，為她塗上(標記)一個與其parent不一樣的color，然後對於每一個edge檢查他所連結的兩個點是否都有不同的顏色。

5.) Finding Strongly Connected Components of a graph A directed graph is called strongly connected if there is a path from each vertex in the graph to every other vertex. (See this for DFS based algo for finding Strongly Connected Components)b

7) Solving puzzles with only one solution, such as mazes. (DFS can be adapted to find all solutions to a maze by only including nodes on the current path in the visited set.)