Depth First Search (DFS) with Explanation and Code

Board Infinity
Board Infinity
Depth First Search (DFS) with Explanation and Code

    Advanced Algorithms and Problem Solving Techniques

    How To Start Competitive Programming - A Complete Guide

    A Quick Guide to Breadth-First Search

    Depth First Search (DFS) with Explanation and Code

    Difference Between BFS and DFS (with code and diagrams)

    How to Perform Level Order Traversal?

    A Quick Guide to Backtracking Algorithm

    Solving N Queens Problem using Backtracking

    Quick Guide to Divide and Conquer Algorithm

    Longest Increasing Subsequence Problem

    Quick Note - Greedy Programming v/s Dynamic Programming

    Coin Change Problem: DP and Recursion Approach

    A Definitive Guide to Knapsack Problem

    How to Solve Subset Sum Problem?

    Understanding Huffman Coding in detail

    Understand the working of KMP Algorithm

    Longest Common Substring Problem

    Longest Common Subsequence problem: solved

    A Quick Guide to Manacher's Algorithm

    Learning About Bipartite Graphs

    Graph Coloring Problem: Explained

    Detect Cycle in Direct Graph

    Directed Acyclic Graph: Representation

    Prim's Algorithm: Explanation, Code, and Applications

    Working of Kruskal's Algorithm

    Prims and Kruskal algorithm for Maximum Spanning Tree

    Bellman Ford Algorithm in detail with code

    Floyd-Warshall Algorithm and its Implementation

    Understand Travelling Salesman Problem

    Branch And Bound Algorithm: Explained

    How to Evaluate Postfix Expression

    Introduction to Round-Robin Scheduling

    Disjoint set (Union find Algorithm)

    State Space Reduction in Algorithms

    Apriori Algorithm

    What is A* Search Algorithm?

Introduction

In this article, you'll learn about the depth-first search algorithm with an example and implementation in C++.

Depth-first search or depth-first traversal is a recursive algorithm for searching all vertices of a graph or tree data structure. Traversing means visiting all nodes of the graph.

Depth First Search Algorithm

Algorithms known as "deep-first search" are used to navigate or search tree or graph data structures. The algorithm starts at the root node (for graphs, choose any node as the root node) and goes as deep as possible along each branch before backtracking.

So the basic idea is to start from the root or any node, mark a node, then move to the next unmarked node and repeat this loop until there are no more unmarked neighbors. is. Then go back and look for other unmarked nodes and traverse them. Finally, print the nodes of the path.

The nodes can be split into two categories. Eventually, all the nodes will be marked as visited.

  1. Visited
  2. Not Visited

Implementation

The goal of this algorithm is to mark each vertex as visited while avoiding cycles.

The DFS algorithm works as follows:

  1. We start by putting any vertex of the graph onto the stack.
  2. Get the top item on the stack and add it to the visited list.
  3. Create a list of neighbors of this node.
  4. Add anything, not in the visit list to the top of the stack.
  5. Repeat #2 & #3 until all nodes are marked as visited

The only problem is that, unlike trees, graphs can contain cycles (a node can be visited twice). To avoid processing a node multiple times, use a boolean visited array. A graph can contain multiple DFS traversals.

Passing the input:

vector<Edge> edges = {
 //node 0 is unconnected
        {1, 2}, {1, 7}, {1, 8}, {2, 3}, {2, 6}, {3, 4}, {3, 5}, {8, 9}, {8, 12}, {9, 10}, {9, 11}
    };

Output: 0, 1,  2,  3,  4,  5,  6,  7,  8,  9,  10,  11,  12

Code

#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;

}


write your code here: Coding Playground

Algorithm Complexity

  • The time complexity of the DFS algorithm is represented in the form of O(V + E), where V = number of nodes & E= is the number of edges.
  • Space Complexity: O(V)

DFS Applications

  • Graph data structure path finding and automation
  • Bipartite graph check
  • To identify strongly connected components in a diagram
  • To detect cycles in a graph