Depth First Search

 What is Depth First Search(DFS) ??

Depth-first-search is an algorithm to search tree or graph data Structure.

We use 4 parameter to implement the dfs algorithm..they are

1. Color

2. Parent(𝛑)

3. Distance(d)

4. Finishing Time (f)

Algorithm DFS

     DFS(G)

1. For each vertex u ∊ V(G)
2. Do color [u]⇠WHITE
3.             π (u) ⇠ NILL
4. time ⇠ 0
5. For each vertex u ∊ V(G)
6.       do if color[u] = WHITE
7.       then DFS_Visit(u)

Algorithm DFS_VISIT

     DFS_Visit(u)

1. color[u] ⇠ GRAY
2. time ⇠ time+1
3. d[u] ⇠ time
4. For each vertex v ∊ ADJ[u]
5. do if color[v]=WHITE
6.         then π[v] ⇠ u
7.               DFS_Visit(v)
8. color[u] ⇠ BLACK
9. f[u] ⇠ time ⇠ time + 1

Here is the example of DFS:--