# Depth First Search (DFS)

Posted By on November 5, 2014

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.

#### Posted by Akash Kurup

Founder and C.E.O, World4Engineers Educationist and Entrepreneur by passion. Orator and blogger by hobby

Website: http://world4engineers.com