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.
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:
DFS // Graph G = <V, E> is the input to DFS time ← 0
each vertex u ∈ V
setColor(u) ← WHITE π(u) ← NIL
each vertex u ∈ V
Color(u) == WHITE
DFS_TRAVERSAL routine is described below :
DFS_TRAVERSAL(u) Time ← time + 1 d[u] ← time setColor(u) ← GRAY
each v ∈ Adjacent[u]
Color(v) == WHITE
π(u) ← u DFS_TRAVERSAL(v)
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|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: Create a DFS forest for the following graph
- 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
- 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: Classify DFS edges of the following graph
DFS traversal and edge labels are shown in the following figure. Here,
T = Tree edge
B = Back edge
F = Forward edge
C = Cross wedge