DFS In Data Structure

In DFS edges are explored out of the most recently discovered vertex (V) that still has unexplored edges leaving it. When all the V’s edges have been explored the search backtracks to explore edges leaving the vertex from which ‘V’ was discovered. This process continues until we have discovered all the vertices that are reachable from the original sources vertex.

if any undiscovered vertices remain then one of them is selected as a new source and the search is repeated. From that source, this entire process is repeated until all vertices are discovered. Unlike BFS the predecessor sub-graph produced by DFS may be compared to several trees because the search may be repeated from multiple sources. DFS also time stamps each vertex ‘V’ has a 2-time stamp which is as follows:

1. The first time stamp d[V] seconds when V is first discovered and the color is grey.
2. The Second time stamp f[V] seconds when the search fills examines V’s adjacency list and blackens ‘V’.

DFS Algorithm with Explanation

DES_(G)

1. For each value $ \le $ V[G]
2. do color [u] $\leftarrow$White
3. $\pi $ [u] $ \gets $ NIL (where stands for parent)
4. time $\gets$ 0
5. for each vertex V $\varepsilon$ V[G]
6. do if color [u] = = white
7. then DES_VISIT (u)

In this algorithm

• Lines 1-3 Paint all vertices white and initialize their $\pi$ field to NIL.
• Line 4 reset the global counter.
• Lines 5-7 check each vertex in V and when a white vertex is found visit it using the DFS visit procedure.

DES_VISIT(u)

1. color[u] $\leftarrow$Grey (what vertex u has just been discovered)
2. time $\leftarrow$ time + 1
3. d[u] $ time
4. for each V $\leftarrow$ adj [u] (explore edge (u,v))
5. do if color [u] == white
6. then $\pi$ [v] = u
7. DES_VISIT (v)
8. color [u] $\gets$ Black (Blacken u, it is finished)
9. f(u) $\gets$ time $\geta$ time+1

• Line 2 implements the global variable time.
• Line 4 records the new value to time as the discovery time d[u]
• Lines 4 – 7 examine each vertex (V) adjacent to u and recursively visit (u) if it is white, and
• finally, in lines 8-9 after every edge leaving u has been explored paint V black and record the finishing time in f(u).

Applications of DFS

Topological Sort:

For a directed cyclic graph G = (V, E) is a linear ordering of vertices such that if G contains an edge (u, v) then (u)appears before (v) in the ordering. A topological sort of graph can be viewed as an ordering of vertices along a horizontal line so that all directed edges go from left to right for every edge (u, v) in a directed acyclic graph. The finish time of (u) is greater than the finish time of (v). Thus, it gives the output containing vertices in reverse order of finish time.

Topological Sort (G)

1. Call DFS(G) to complete finishing time F(u)
2. As each vertex is finished insert it onto the front of a link list
3. Return the link list of vertices.

Finding the Strongly Connected Components of Graph:

Vertices of a directed graph are in the same component if and only if they are reachable from each other. A strongly connected directed graph is a maximal sort of vertices such that for every pair of vertices (u,v) there is a directed path from u to v and vice versa.

Strongly_Connected_Components (G)

1. Call DFS(G) to compute f(u) for each vertex u.
2. compute G^T
3. Call DFS (GT) but in the main loop of DFS. Consider the vertices in order of decreasing f(v).
4. The output of the vertices of each time in the Depth First Forest.