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.


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,

Animated Example of Depth First Search
Animated Example of Depth First Search

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.