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

  • 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.
Depth First Search traversal
DFS Traversal order of nodes
  • 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.

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
  • 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|2).
  • 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|2).

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

DFS traversal

Solution:

Depth First Search example
  • 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.
Example of Depth First Search

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.

Graph G
Edge types in DFS
DFS traversal and edge classification of G
Edges in Depth First Search
DFS forest and edge classification of G

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