# Depth First Search (DFS)

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.

**Analysis**

The analysis is similar to that of BFS analysis. The DFS-Visit is called (from DFS or from itself) once for each vertex in V[G] since each vertex is changed from white to gray once. The for-loop in DFS-Visit is executed a total of |E| times for a directed graph or 2|E| times for an undirected graph since each edge is explored once. Moreover, initialization takes Θ(|V|) time. Therefore, the running time of DFS is Θ(V + E).

Note that its Θ, not just O, since guaranteed to examine every vertex and edge.

Consider vertex *u* and vertex *v* in V[G] after a DFS. Suppose vertex *v* in some DFS-tree. Then we have d[*u*] < d[*v*] < f[*v*] < f[*u*] because of the following reasons:

1. Vertex *u* was discovered before vertex *v*; and

2. Vertex *v* was fully explored before vertex *u* was fully explored.

Note that converse also holds: if d[*u*] < d[*v*] < f[*v*] < f[*u*] then vertex *v* is in the same DFS-tree and a vertex *v* is a descendent of vertex *u*.

Suppose vertex *u* and vertex *v* are in different DFS-trees or suppose vertex *u* and vertex *v* are in the same DFS-tree but neither vertex is the descendent of the other. Then one vertex was discovered and fully explored before the other was discovered i.e., f[*u*] < d[*v*] or f[*v*] < d[*u*].

**Parenthesis Theorem** For all *u*, *v*, exactly one of the following holds:

1. d[*u*] < f[*u*] < d[*v*] < f[*v*] or d[*v*] < f[*v*] < d[*u*] < f[*u*] and neither of *u* and *v* is a descendant of the other.

2. d[*u*] < d[*v*] < f[*v*] < f[*u*] and *v* is a descendant of *u*.

3. d[*v*] < d[*u*] < f[*u*] < f[*v*] and *u* is a descendant of *v*.

[Proof omitted.]

So, d[*u*] < d[*v*] < f[*u*] < f[*v*] cannot happen. Like parentheses: ( ) [], ( [ ] ), and [ ( ) ] are OK but ( [ ) ] and [ ( ] ) are not OK.