What is DFS Algorithm? Depth First Search Algorithm Explained

The Depth-First Search algorithm is critical when working with data structures. Its recursive nature helps individuals examine and collect data by joining the vertices of a graph or a tree data structure. DFS in data structure have played a crucial role in searching for DFS trees and graph designs. 

The DFS algorithm has proven to be extremely important in studying data structures. This algorithm follows the backtracking principle for performing exhaustive searches of multiple nodes by backtracking as and when required and moving forward when possible. It works node-to-node by pushing the stack from one step to another.

Depth-First Search Algorithm Defined

The Depth-First Search algorithm or DFS algorithm is a way to explore various data structures. It traverses and provides search results on data structures such as trees and graphs. As it is in the form of a tree, the search starts at the first node, the tree’s root node. In the case of a graph, any node can be taken as the root node or the starting point.

The DFS algorithm searches each node by moving forward and backtracking as far as possible. When the iteration hits rock bottom, the Depth-First Search algorithm explores the network in a depthward motion. It hence opts for the next vertex to start the traversal using a stack data structure.

Working of a Depth-First Search Algorithm

The functioning of the DFS algorithm is illustrated below:

• Step 1: Create a stack with the total number of vertices in a graph.
• Step 2: Select any node in a graph as the root note, start traversing through the vertices, and push the stack from one vertex to the other.
• Step 3: Push the stack to a non-visited vertex adjacent to the visited one.
• Step 4: Repeat the previous step as far as possible until the stack reaches the last vertex. 
• Step 5: If there are no vertices left to visit, go back to the stack and pop a vertex from it.
• Step 6: Repeat the previous three steps till the stack becomes empty.

Graph Traversal Algorithm

Graph traversal is a technique used to search and locate a vertex in a graph. The search technique evaluates the graph’s order to traverse each vertex. Graph traversal helps shorten the search steps and finds the required edges to be involved in a search process without creating loops.

There are two ways in which a graph can be traversed — Depth-First Search (DFS) algorithm and Breadth-First Search (BFS) algorithm. Hence, the DFS algorithm is a part of the graph traversal algorithm.

Enrol for the Machine Learning Course from the World’s top Universities. Earn Master, Executive PGP, or Advanced Certificate Programs to fast-track your career.

Illustration of Depth-First Search Algorithm

Here is an example to better understand the working of a DFS algorithm.

An undirected graph with 5 vertices has been taken to perform the DFS algorithm. The traversal starts at vertex 0 by initiating the DFS algorithm as it places itself in the visited list, and the remaining adjacent vertices are placed in the stack.

Then we move to the next adjacent unvisited vertex, which is 1. Since we have already visited 0, the stack is pushed to the next adjacent vertex, 2.

The adjacent vertex to 2, yet to be visited, is vertex 4. Now vertex 4 is added to the stack top so that the traversal to vertex 4 can occur.

The last node in this graph is vertex 3 without any unvisited adjacent vertex. Hence, all the nodes in the graph have been visited, marking the end of the Depth First Search algorithm for this graph.

Register for upGrad’s MS in Full Stack AI and ML to get an insight into the Depth First Search algorithm and learn its importance in data structures.

Depth-First Search Algorithm Pseudocode

The pseudocode for the DFS algorithm is very short and crisp. It is a concise programming statement that can be implemented in multiple programming languages such as Java, Python, C, C++, etc.

The graph is stored in A, whereas the starting or root node is in B.

Recursive pseudocode

DFS (Graph a, node b):

        mark b as visited

        for neighbors adj_node of b in Graph A:

            if adj_node is not visited:

                DFS (A, adj_node)

Iterative pseudocode

DFS(A, b): 

      let St be stack

      Push b in the stack

      mark b as visited.

      while ( St is not empty)

          v  =  Node at the top of stack

          remove the node from stack

         for all neighbors adj_node of v in Graph A:

            if adj_node is not visited :

                     mark adj_node as visited

                     push adj_node in stack 

Complexity Of Depth-First Search Algorithm

if the traversal of the entire data structure or graph has been completed, then the temporal complexity of Depth-First Search is O(V), where V denotes the number of vertices in the data structure.

The following explanations can be derived by representing the graph in an adjacency list:

• Each of the vertices in the data structure keeps track of nearby nodes and edges. Let’s imagine V is the total number of vertices and E is the total number of edges in the graph.
• Now we can derive the temporal complexity through the following equation: O(V) + O(E) = O(V + E).

However, the space complexity of the Depth First Search algorithm is O(V).

Use Cases Of Depth-First Search Algorithm

The Depth First Search algorithm has a wide range of applications, making this technique extremely important when working with data structures. The following are the use cases of DFS algorithm:

• Detecting the cycle of a graph: This technique is used to identify the cycle of a graph and detect whether it has a proper cycle. A graph is said to have a proper cycle only if the back edge of a node is visible during the traversal process. Hence, the DFS algorithm is applied to find and detect graphs containing rear edges.
• Conducting topological sorting: Topological sorting is an important aspect used to prepare a proper schedule of jobs based on the dependencies between them. Sorting is performed especially in computer science when there is a possibility of scheduled instructions and for the evaluation formula cell. The DFS algorithm is used to recalculate the formula value for the spreadsheets for better compilation of jobs, arranging serial-wise data, and detecting symbol dependencies for convenience of data representation.
• Determining whether a graph is bipartite: The DFS technique marks and colours a vertex when it is first discovered. It helps to prevent connecting vertices of the same colour to a single node edge. However, the first vertex of a connected component can be either black or red.
• Locating strong components in a graph: Components are strongly connected when each graph vertex is directed and well-connected with the path of every other vertex. The DFS algorithm is crucial in finding those strongly connected components in a tree structure or graph.
• Solving mazes and puzzles: The DFS algorithm is applied to solve multiple puzzles and mazes by locating the keys and including the notes in the visited sets of the current path. It acts as a means of one solution to numerous problems while solving a puzzle.
• Finding a path in a graph: This technique is a masterstroke for conveniently finding and locating paths between two specific vertices. It is a very efficient algorithm involving minimum chances of errors.

Implementing Code Of Depth-First Search Algorithm

Code implementation of the Depth-First Search algorithm can be classified based on various programming languages as enumerated below:

Depth First Search Python

def DFS(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)

    print(start)

    for next in graph[start] - visited:
        DFS(graph, next, visited)
    return visited

graph = {'0': set(['1', '2']),

         '1': set(['0', '3', '4']),
         '2': set(['0']),
         '3': set(['1']),
         '4': set(['2', '3'])}

DFS(graph, '0')

Depth-First Search Java

// DFS algorithm in Java

import java.util.*;

class Graph {

  private LinkedList<Integer> adjLists[];

  private boolean visited[];

  // Graph creation

  Graph(int vertices) {

    adjLists = new LinkedList[vertices];

    visited = new boolean[vertices];

    for (int i = 0; i < vertices; i++)

      adjLists[i] = new LinkedList<Integer>();

  }

  // Add edges

  void addEdge(int src, int dest) {

    adjLists[src].add(dest);

  }

  // DFS algorithm

  void DFS(int vertex) {

    visited[vertex] = true;

    System.out.print(vertex + " ");

    Iterator<Integer> ite = adjLists[vertex].listIterator();

    while (ite.hasNext()) {

      int adj = ite.next();

      if (!visited[adj])

        DFS(adj);

    }

  }

  public static void main(String args[]) {

    Graph g = new Graph(4);

    g.addEdge(0, 1);

    g.addEdge(0, 2);

    g.addEdge(1, 2);

    g.addEdge(2, 3);

    System.out.println("Following is Depth First Traversal");

    g.DFS(2);

  }

}

Sign up for the Advanced Certificate Program to better understand ‘what is DFS algorithm’ and how it works.

Depth-First Search C++

// DFS algorithm in C++

#include <iostream>

#include <list>

using namespace std;

class Graph {

  int numVertices;

  list<int> *adjLists;

  bool *visited;

   public:

  Graph(int V);

  void addEdge(int src, int dest);

  void DFS(int vertex);

};

// Initialize graph

Graph::Graph(int vertices) {

  numVertices = vertices;

  adjLists = new list<int>[vertices];

  visited = new bool[vertices];

}

// Add edges

void Graph::addEdge(int src, int dest) {

  adjLists[src].push_front(dest);

}

// DFS algorithm

void Graph::DFS(int vertex) {

  visited[vertex] = true;

  list<int> adjList = adjLists[vertex];

  cout << vertex << " ";

  list<int>::iterator i;

  for (i = adjList.begin(); i != adjList.end(); ++i)

    if (!visited[*i])

      DFS(*i);

}

int main() {

  Graph g(4);

  g.addEdge(0, 1);

  g.addEdge(0, 2);

  g.addEdge(1, 2);

  g.addEdge(2, 3);

  g.DFS(2);

  return 0;

}

You can also check out our free courses offered by upGrad in Management, Data Science, Machine Learning, Digital Marketing, and Technology. All of these courses have top-notch learning resources, weekly live lectures, industry assignments, and a certificate of course completion – all free of cost!

Conclusion

The role of the Depth-First Search algorithm in working with data structures and deriving meaningful results is unquestionable. It is a great tool widely used in today’s technological industry, with a projected boom in its use in future. 

If you are a tech professional looking to learn DFS algorithm in detail, you can consider upGrad’s Advanced Certificate Programme in Machine Learning & NLP from IIITB. The course offers a practical understanding with its cutting-edge curriculum designed specifically for working professionals.