Blog_Banner_Asset
    Homebreadcumb forward arrow iconBlogbreadcumb forward arrow iconArtificial Intelligencebreadcumb forward arrow iconWhat is DFS Algorithm? Depth First Search Algorithm Explained

What is DFS Algorithm? Depth First Search Algorithm Explained

Last updated:
26th Jul, 2023
Views
Read Time
9 Mins
share image icon
In this article
Chevron in toc
View All
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.

Ads of upGrad blog

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)

Top Machine Learning and AI Courses Online

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.

In-demand Machine Learning Skills

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;

}
Ads of upGrad blog

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. 

Profile

Pavan Vadapalli

Blog Author
Director of Engineering @ upGrad. Motivated to leverage technology to solve problems. Seasoned leader for startups and fast moving orgs. Working on solving problems of scale and long term technology strategy.
Get Free Consultation

Select Coursecaret down icon
Selectcaret down icon
By clicking 'Submit' you Agree to  
UpGrad's Terms & Conditions

Our Popular Machine Learning Course

Frequently Asked Questions (FAQs)

1What is the data structure of DFS?

The depth-First Search algorithm uses a forward-moving and backtracking technique and the depthward motion, whereas the stack is used to remember the next vertex. Then a fresh start of the search emerges from the existing vortex and continues till the end of the graph. The DFS algorithm in data structure exists in a tree structure or graph.

2What is the difference between DFS and BFS (Breadth First Search)?

The major difference between the Depth-First Search (DFS) and Breadth-First Search (BFS) algorithm is that DFS uses the stack data structure and the depthward motion from one vertex to the other, whereas BFS chooses the cute data structure to identify the shortest path in a graph.

3How does the DFS algorithm handle cycles in a graph?

The DFS technique is based on the idea that a cycle in a graph exists only when there is an existence of a back edge in the graph. This means that a present node directs to one of its preceding nodes present in the graph.

Explore Free Courses

Suggested Blogs

Artificial Intelligence course fees
5411
Artificial intelligence (AI) was one of the most used words in 2023, which emphasizes how important and widespread this technology has become. If you
Read More

by venkatesh Rajanala

29 Feb 2024

Artificial Intelligence in Banking 2024: Examples &#038; Challenges
6144
Introduction Millennials and their changing preferences have led to a wide-scale disruption of daily processes in many industries and a simultaneous g
Read More

by Pavan Vadapalli

27 Feb 2024

Top 9 Python Libraries for Machine Learning in 2024
75590
Machine learning is the most algorithm-intense field in computer science. Gone are those days when people had to code all algorithms for machine learn
Read More

by upGrad

19 Feb 2024

Top 15 IoT Interview Questions &#038; Answers 2024 – For Beginners &#038; Experienced
64449
These days, the minute you indulge in any technology-oriented discussion, interview questions on cloud computing come up in some form or the other. Th
Read More

by Kechit Goyal

19 Feb 2024

Data Preprocessing in Machine Learning: 7 Easy Steps To Follow
152828
Summary: In this article, you will learn about data preprocessing in Machine Learning: 7 easy steps to follow. Acquire the dataset Import all the cr
Read More

by Kechit Goyal

18 Feb 2024

Artificial Intelligence Salary in India [For Beginners &#038; Experienced] in 2024
908705
Artificial Intelligence (AI) has been one of the hottest buzzwords in the tech sphere for quite some time now. As Data Science is advancing, both AI a
Read More

by upGrad

18 Feb 2024

24 Exciting IoT Project Ideas &#038; Topics For Beginners 2024 [Latest]
759786
Summary: In this article, you will learn the 24 Exciting IoT Project Ideas & Topics. Take a glimpse at the project ideas listed below. Smart Agr
Read More

by Kechit Goyal

18 Feb 2024

Natural Language Processing (NLP) Projects &amp; Topics For Beginners [2023]
107656
What are Natural Language Processing Projects? NLP project ideas advanced encompass various applications and research areas that leverage computation
Read More

by Pavan Vadapalli

17 Feb 2024

45+ Interesting Machine Learning Project Ideas For Beginners [2024]
328212
Summary: In this Article, you will learn Stock Prices Predictor Sports Predictor Develop A Sentiment Analyzer Enhance Healthcare Prepare ML Algorith
Read More

by Jaideep Khare

16 Feb 2024

Schedule 1:1 free counsellingTalk to Career Expert
icon
footer sticky close icon