# Algorithm for Depth First Search of a Graph and its example

**Algorithm Depth-First Search**

The DFS forms a depth-first forest comprised of more than one depth-first trees. Each tree is made of edges (*u*, *v*) such that *u* is gray and *v* is white when edge (*u*, *v*) is explored. The following pseudocode for DFS uses a global timestamp time.

**DFS (V, E)**

1. **for** each vertex *u* in V[G]

2. **do** color[*u*] ← WHITE

3. π[*u*] ← NIL

4. time ← 0

5. **for** each vertex *u* in V[G]

6. **do if** color[u] ← WHITE

7. **then** DFS-Visit(*u*) ▷ build a new DFS-tree from *u*

**DFS-Visit(u)**

1. color[u] ← GRAY ▷ discover *u*

2. time ← time + 1

3. d[u] ← time

4. **for** each vertex *v* adjacent to *u* ▷ explore (*u*, *v*)

5. **do if** color[*v*] ← WHITE

6. **then** π[*v*] ← *u*

7. DFS-Visit(*v*)

8. color[*u*] ← BLACK

9. time ← time + 1

10. f[*u*] ← time ▷ we are done with *u*

**Example (CLRS)**: In the following figure, the solid edge represents discovery or tree edge and the dashed edge shows the back edge. Furthermore, each vertex has two time stamps: the first time-stamp records when vertex is first discovered and second time-stamp records when the search finishes examining adjacency list of vertex.