# Graph Traversal - DFS
###### tags: `DS` `DFS` `GRAPH` `ch6` `Adjacency Lists`

| | DFS | BFS |
| ------------------------- | ------ | ------ |
| 輔助的DS | Stack | Queue |
| 相鄰串列(Adjacency Lists) | O(n+e) | O(n+e) |
| 相鄰矩陣(Adjacency Matrix)| O(n**2) | O(n**2) |

## DS版本 (皆對無向圖) (採用Adjacenty Lists)

DFS(Vertex V of Graph G){
    //Assume have a global array visited[1..n] of boolean
    //n = num of v
    visited[v] = True; // becuz vertex already visited.
    foreach(vertex w adjacency to v do){
        if(visited[w] == false) DFS(w);
    }
}

**Note:** DFS order並不唯一，故通常會設定值小者優先，如此會唯一。

## Algo版本 (對有向圖) (採用Adjacenty Lists)
Note: the **u.d** and **u.f** in DFS-visit is...
1. u.d == the **discovered** time of u.
2. u.f == the **finished** time of u.
3. u.color == White (haven't been vistied)
4. u.color == Gray (already visit but the adjacency vertex of u didn't finish yet)
5. u.color == Black (finished visit)

keyPoint!
1. every vertex **before visit is white!**
2. every vertex **before visit is NULL!**
3. every vertex **should be checked whether color is white before visit**, if true then visit!

DFS(Graph G){ // initialize the graph
    foreach(vertex u belongs to G.V do){
        u.color = white;
        u.pi = NULL;
    }
    time = 0;
    foreach(vertex u belongs to G.V do){
        if(u.color == white) DFS-visit(G, u);
    }
}

DFS-visit(G, u){
    time += 1;
    u.d = time;
    u.color = Gray;
    foreach(v belongs to G.Adj[u]){
        if(v.color == white){
            v.pi = u;
            DFS-visit(G, v);
        }        
    }
    time += 1;
    u.color = Black;
    u.f = time;
}

## DFS有向圖, 邊的種類有分四種(詳記顏色意義)
1. Tree Edge:
DFS經過的edge, (u,v) -> v is White.
2. Back Edge:
回到祖先的edge, (u,v) -> v is Gray.
3. Forward Edge:
指向後代的edge, (u,v) -> v is Black.
4. Cross Edge:
跨越不同子樹的edge
判斷:(u,v) is Black,可能為Forward or Cross edge 須根據以下情況判斷...

    if(u.d < v.d) then (u,v) is Forward.
    else Cross edge.