Depth First Search – Graph Traversal Method

Depth First Search is a very useful way of graph traversal in many computer science applications. It uses a stack to traverse the graph.

Recommended Reading: Basics of Graphs

Working Mechanism of Depth First Search

• In graph traversal tree, root of the tree would be the node from where we started traversal process. It is closely related to pre-order traversal of tree. It explores the branch as deep as possible before backtracking and exploring another branch.
• Following figure shows the order of visited nodes in DFS traversal. Starting from root node, it explores the left branch and recursively calls its left child until there is no more left child. After reaching the leaf node, it visits the right child in same order and then backtracks to its parent.

• To simplify the procedure and to keep track of already visited vertices, we use time stamps. Two time stamps are associated with each vertex, value of time stamps vary from 1 to 2|v|. When vertex is encountered first time, it is called discovery of the vertex.
• On discovery of vertex u, time stamp d[u] is associated with that vertex, which is called discovery time of u.
• Similarly, when algorithm backtracks from any vertex u, it is assigned finishing time f[u].
• It is very obvious that each vertex v ∈ G, d[u] < f[u]. We will use color coding to indicate states for the nodes.
  • Vertex u will be white before it is discovered, that is before it is assigned d[u].
  • Vertex u will be gray between its discovery and finishing, that is between d[u] and f [u].
  • Vertex u will be black after algorithm backtracks from u, that is after assignment of f [u].
• DFS searches deeper and deeper in graph whenever it is possible.
• Unlike BFS, the sub graph created by DFS might have several trees. In other words, DFS traversal may produce DFS tree or DFS forest.

Algorithm for Depth First Search

Algorithms for DFS traversal is shown below:

Algorithm

 DFS
// Graph G = <V, E> is the input to DFS

time ← 0

for

each vertex u ∈ V 

do

  setColor(u) ← WHITE	
  π(u) ← NIL

end

for

each vertex u ∈ V 

do

if

 Color(u) == WHITE 

then

    DFS_TRAVERSAL(u)
  

end

end

DFS_TRAVERSAL routine is described below :

DFS_TRAVERSAL(u)
Time ← time + 1
d[u] ← time
setColor(u) ← GRAY

for

each v ∈ Adjacent[u] 

do

if

Color(v) == WHITE 

then

    π(u) ← u
    DFS_TRAVERSAL(v)
  

end

end

setColor(u) ← BLACK
time ← time + 1
f[u] ← time

Complexity Analysis of Depth First Search

• In worst case, every edge and vertex will be explored by algorithm. So time complexity of algorithm is O(|V| + |E|). Number of edged depends on how sparse the graph is? In worst case, |E| would be O(|V|²).
• In worst case, DFS traversal need stack of size V to store vertices. Mostly this is required in case of skew tree.
• With adjacency list representation, it requires O(|V| + |E|) space. Space complexity in case of adjacency matrix representation would be O(|V|²).

Applications of DFS

• Finding connected components of graph.
• Topological sorting.
• Finding strongly connected component.
• Check the cycle in undirected graph.
• Game playing.
• Checking biconnectivity of graph.
• Finding articulation point.

Example

Example: Create a DFS forest for the following graph

Solution:

• Initially,none of the vertex is visited, so they are white. On discovering vertex first time, it is converted to gray. When no more unvisited child exists for vertex, it is considered finished and converted to black.
• Discovery time and finish time is written beside each vertex separated by
  slash (/).
• DFS Forest of above graph is shown below. Dotted edge indicates back edges. We get three DFS tree.

Classification of DFS edges

Edges of DFS forest are classified in one for the four categories :

Tree edges : In the depth-first forest, edge (u, v) is considered tree edge if v was first discovered by exploring edge (u, u).

Back edge : In the depth-first tree, edge (u, v) is called back edge if edge (u, v) connects a vertex u to an ancestor v. Self-loop is considered as back edge.

Forward edge : Forward edge (u, v) is the non-tree edge that connects vertex v to its descendent in the depth-first tree.

Cross edge : Remaining all edges is classified as cross edges.

The following example illustrates the DFS forest and the types of edges associated with it.

Example

Example: Classify DFS edges of the following graph

Solution:

DFS traversal and edge labels are shown in the following figure. Here,

T =  Tree edge

B =  Back edge

F =  Forward edge

C = Cross wedge