Graphs are useful in a lot of practical scenarios like in fields of networking, game theory and social media among many others. Often situations involving graphs involves traversal of the graph. In this post we are going to talk about one such graph traversal technique, Depth First Search.

Note : In all the pseudo codes, 0-based indexing is used and the indentations are used to differentiate between block of codes.

Depth First Search or DFS

Depth First Search or DFS is a traversal or searching algorithm for graph and graph-like data structures that uses the concept of backtracking and exhaustive searching. In this variation of graph traversal, we traverse the depth of the graph first before traversing the breadth of the graph.

The basic idea here is to start at the root (or a random node for graph) and explore as far as possible in each branch before backtracking i.e. in DFS, once we pick a branch we continue moving on that branch until we reach the end of the branch, after which we backtrack to pick some other branch.

For example,

In the above graph we picked node 1 as the root, however this choice is arbitrary for a graph.

Algorithm

Recursive

Pseudo Code :

``````graph[V][V]
visited[V]={false}

dfs(int node)
visited[node]=true
for child in graph[node]
if visited[child]=true
continue
dfs(child)``````

Iterative

Pseudo Code :

``````graph[V][V]
visited[V]={false}

dfs(int root)
stack dfs_stack
dfs_stack.push(root)
visited[root]=true
while dfs_stack.empty==false
node=dfs_stack.top
dfs_stack.pop
for child in graph[node]
if visited[child]=true
continue
visited[child]=true
dfs_stack.push(child)``````

Time Complexity : O(V+E)

Space Complexity : O(V)

where V is the number of vertices and E is the number of edges.

Application

• The DFS of a weighted graph produces a Minimum Spanning Tree of the graph.
• DFS can be used to detect cycles in the graph.
• DFS can be used to find a path between any two vertices in a graph.
• DFS can be used for performing Topological Sort.
• DFS is also used by Search Engines for web crawling.
• DFS is also used in the field of Artificial Intelligence in search-based models.

Note : Due to the infinitely big sized graphs in practical situations, often a restricted version of DFS is also used where we only traverse to a limited depth before backtracking.

Depth First Traversal is only one form of graph traversal and there are other methods also to traverse the graph but I will discuss them in other posts.