Depth First Search in Data Structure

A graph is a non-linear data structure. Therefore, its traversing requires special algorithms. There are majorly two ways to traverse a tree or a graph: Depth-first search and breadth-first search.

Depth First Search is a traversal technique in which we follow a depth-wise motion to traverse all the nodes. This technique is based on backtracking.

What is DFS:

Depth first search is a recursive technique to traverse all the nodes of a graph. It makes use of the stack data structure for traversing and remembering the nodes.

DFS follows the backtracking approach i.e. whenever there are no more nodes in the current path, it goes back to the initial node and starts traversing the next available path.

While using the stack, we first choose the initial node and push all its adjacent nodes into the stack. To visit a node, we pop a node from the stack and push all its adjacent nodes to the stack.

This goes on until all the nodes are popped out i.e. the stack is empty. In the whole process, we need to make sure that we don’t visit the same node more than once, especially if the cycle exists. The output of DFS is always in the form of a spanning tree.

Algorithm:

Step 1: Algorithm DFS(vertex v)
Step 2: visited[v] = 1
Step 3: for all nodes ‘w’ adjacent to v:
if(visited[w] == 0):
DFS(w)
Step 4: End for loop
Step 5: End DFS

Working of DFS in an Undirected Connected Graph:

Before looking at the working of the algorithm, let us first understand the following terms:

Visit: It means we reached the node or we are reaching the node.
Explore: It means processing every child of the node.
Discovery: This term is used when we visit a node for the first time.

In DFS, we can take any node as the initial node and start traversing its adjacent nodes. Let us see the working of DFS with the help of the following example:

Let’s start with node A. once we reach the child of A, we start exploring the grandchild of A i.e. the child of B and so on. In this manner, we will traverse the whole graph.

We go from A to B to D to H. when we reach H, we have 3 choices: E, F, G. We can choose to go with any of them. Let us go with F. from F, we got to C as C is the only unvisited node of F.

Similarly, from C we will visit G. Now G does not have any unvisited node. Therefore, G is the dead node and we will backtrack from here.

Thus, the spanning tree formed by following this path will be:

The push and pop operations in the stack will be:

Thus, the path followed is A→B→D→H→F→C→G→E. We need to note that there could multiple paths for the same graph depending upon which node is traversed first.

DFS on a Directed Graph:

For a directed graph, the output of the DFS algorithm will be either a spanning tree or a spanning forest depending upon whether the graph is connected or disconnected.

Consider the following graph having 4 nodes:

If we perform DFS on this graph, the possible spanning trees will be:

In the first spanning tree, we have followed A→B→C→D whereas in the second spanning tree we have followed A→D→C→B.

Implementation of DFS in C:

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX 5

struct node{
   char label;
   bool visited;
};

int Stack[MAX]; 
int top = -1; 
struct node* lstNodes[MAX];
int adjMatrix[MAX][MAX];
int nodeCount = 0;

void push(int item) { 
   Stack[++top] = item; 
} 

int pop() { 
   return Stack[top--]; 
} 

int peek() {
   return Stack[top];
}

bool isStackEmpty() {
   if(top == -1)
    return;
}
void addNode(char label) {
   struct node* n = (struct node*) malloc(sizeof(struct node));
   n->label = label;  
   n->visited = false;     
   lstNodes[nodeCount++] = n;
}
void addEdge(int Start,int End) {
   adjMatrix[Start][End] = 1;
   adjMatrix[End][Start] = 1;
}

void display_node(int nodeIndex) {
   printf("%c ",lstNodees[nodeIndex]->label);
}       

int get_adj_unvisited_node(int nodeIndex) {
   int i;
   for(i = 0; i < nodeCount; i++) {
      if(adjMatrix[nodeIndex][i] == 1 && lstnodees[i]->visited == false) {
         return i;
      }
   }
   return -1;
}

void DFS() {
   int i;
   lstNodes[0]->visited = true;
   display_node(0);   
   push(0);
   while(!isStackEmpty()) {
      int unvisited_node = get_adj_unvisited_node(peek());
      if(unvisited_node == -1) {
         pop();
      } 
      else {
         lstNodes[unvisited_node]->visited = true;
         display_node(unvisited_node);
         push(unvisited_node);
      }
   }      
   for(i = 0; i < nodeCount; i++) {
      lstNodees[i]->visited = false;
   }        
}

int main() {
   int i, j;
   for(i = 0; i < MAX; i++) {
      for(j = 0; j < MAX; j++) 
         adjMatrix[i][j] = 0;
   }

   addNode('A');   
   addNode('B'); 
   addNode('C');  
   addNode('D');  
   addNode('E');  

   addEdge(0, 1);   
   addEdge(0, 2);    
   addEdge(0, 3);    
   addEdge(1, 4);    
   addEdge(2, 4);    
   addEdge(3, 4);    

   printf("Depth First Search: ")
   DFS(); 

   return 0;   
}

Implementation of DFS in C++

#include <bits/stdc++.h>
using namespace std;

class graph
{
public:
  map<int, bool> visited;
  map<int, list<int>> adjacent;
  void addEdge(int v, int w);
  void DFS(int v);
};

void graph::addEdge(int v, int w)
{
  adjacent[v].push_back(w); 
}

void graph::DFS(int v)
{
  visited[v] = true;
  cout << v << " ";
  list<int>::iterator i;
  for (i = adjacent[v].begin(); i != adjacent[v].end(); ++i)
    if (!visited[*i])
      DFS(*i);
}

int main()
{
  graph g;
  g.addEdge(0, 1);
  g.addEdge(0, 9);
  g.addEdge(1, 2);
  g.addEdge(2, 0);
  g.addEdge(2, 3);
  g.addEdge(9, 3);
  cout << "The Depth First Traversal is: \n";
  g.DFS(1);
  return 0;
}

DFS Implementation in Java:

import java.io.*;
import java.util.*;
class Graph {
  private int V; 
  private LinkedList<Integer> adjacent[];
  @SuppressWarnings("unchecked") graph(int v)
  {
    V = v;
    adjacent = new LinkedList[v];
    for (int i = 0; i < v; ++i)
      adjacent[i] = new LinkedList();
  }
  void addEdge(int v, int w)
  {
    adjacent[v].add(w); 
  }
  void DFSUtil(int v, boolean visited[])
  {
    visited[v] = true;
    System.out.print(v + " ");
    Iterator<Integer> i = adjacent[v].listIterator();
    while (i.hasNext())
    {
      int n = i.next();
      if (!visited[n])
        DFSUtil(n, visited);
    }
  }
  void DFS(int v)
  {
    boolean visited[] = new boolean[V];
    DFSUtil(v, visited);
  }

  public static void main(String args[])
  {
    graph g = new Graph(5);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 3);
    g.addEdge(2, 0);
    g.addEdge(2, 3);
    g.addEdge(3, 4);

    System.out.println("The Depth First Traversal is: \n");
    g.DFS(1);
  }
}

Implementation of DFS in Python:

from collections import defaultdict
class Graph:
  def __init__(self):
    self.graph = defaultdict(list)
  def addEdge(self, w, v):
    self.graph[w].append(v)
  def DFSUtil(self, v, visited):
    visited.add(v)
    print(v, end=' ')
    for adjacent in self.graph[v]:
      if adjacent not in visited:
        self.DFSUtil(adjacent, visited)
  def DFS(self, v):
    visited = set()
    self.DFSUtil(v, visited)

g = Graph()
g.addEdge(0, 1)
g.addEdge(0, 2)
g.addEdge(1, 3)
g.addEdge(2, 3)
g.addEdge(2, 0)
g.addEdge(3, 3)

print("The DFS is: ")
g.DFS(1)

Handling Disconnected graphs:

In a disconnected graph, not all the nodes are reachable from the source node. Thus, in the case of disconnected graphs, we need to handle an extra corner case.

Algorithm:

Step 1: Take any node as the starting or the source node.
Step 2: Formulate a recursive function to input the index of the node and the visited array.
Step 3: From the source node, move to its adjacent node.
Step 4: Mark it(the current node) as visited.
Step 5: Traverse all the connected nodes by following the above steps and mark them as visited.
Step 6: Run a loop from 0 to n-1 i.e. for all the nodes to check if any of them is left unvisited.
Step 7: If an unvisited node still exists, reach it and mark it as visited.

DFS on an Undirected, Disconnected graph:

Depth first traversal on a disconnected graph does not give a spanning tree as its output. Rather, it gives a spanning tree forest or a forest of spanning trees. Let us take the following disconnected graph:

Let us start traversing from node A. After traversing A, we will move from B to C to D. Then, we will start from E and move from F to G to H and then from I to J to K. Thus, three spanning trees will form which we call the forest of spanning trees as shown:

Thus, the output of a DFS could be either a spanning tree or a spanning forest.

Implementation for Disconnected graph in C++

#include <bits/stdc++.h>
using namespace std;

class Graph {
  void DFSUtil(int v);

public:
  map<int, bool> visited;
  map<int, list<int>> adj;
  void addEdge(int v, int w);
  void DFS();
};

void Graph::addEdge(int v, int w)
{
  adjacent[v].push_back(w); 
}

void Graph::DFSUtil(int v)
{
  visited[v] = true;
  cout << v << " ";
  list<int>::iterator i;
  for (i = adjacent[v].begin(); i != adjacent[v].end(); ++i)
    if (!visited[*i])
      DFSUtil(*i);
}

void Graph::DFS()
{
  for (auto i:adjacent)
    if (visited[i.first] == false)
      DFSUtil(i.first);
}

int main()
{
  Graph g;
  g.addEdge(0, 1);
  g.addEdge(0, 9);
  g.addEdge(1, 3);
  g.addEdge(2, 1);
  g.addEdge(2, 3);
  g.addEdge(9, 3);

  cout << "The Depth First Traversal is: \n";
  g.DFS();
  return 0;
}

Implementation for Disconnected graph in Java:

import java.io.*;
import java.util.*;
class Graph {
  private int V; 
  private LinkedList<Integer> adjacent[];
  @SuppressWarnings("unchecked") Graph(int v)
  {
    V = v;
    adj = new LinkedList[v];
    for (int i = 0; i < v; ++i)
      adjacent[i] = new LinkedList();
  }
  void addEdge(int v, int w)
  {
    adj[v].add(w); 
  }
  void DFSUtil(int v, boolean visited[])
  {
    visited[v] = true;
    System.out.print(v + " ");
    Iterator<Integer> i = adjacent[v].listIterator();
    while (i.hasNext()) {
      int n = i.next();
      if (!visited[n])
        DFSUtil(n, visited);
    }
  }

  void DFS()
  {
    boolean visited[] = new boolean[V];
    for (int i = 0; i < V; ++i)
      if (visited[i] == false)
        DFSUtil(i, visited);
  }
  
  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, 0);
    g.addEdge(2, 3);
    g.addEdge(3, 3);
    System.out.println("The Depth First Traversal is: ");
    g.DFS();
  }
}

DFS Implementation for Disconnected graph in Python:

from collections import defaultdict
class Graph:
  def __init__(self):
    self.graph = defaultdict(list)
  def addEdge(self, w, v):
    self.graph[u].append(v)
  def DFSUtil(self, v, visited):
    visited.add(v)
    print v,
    for adjacent in self.graph[v]:
      if adjacent not in visited:
        self.DFSUtil(adjacent, visited)

  def DFS(self):
    visited = set()
    for node in list(self.graph):
      if node not in visited:
        self.DFSUtil(node, visited)

g = Graph()
g.addEdge(0, 1)
g.addEdge(0, 2)
g.addEdge(1, 2)
g.addEdge(2, 0)
g.addEdge(2, 3)
g.addEdge(3, 3)
print "The Depth First Traversal is: "
g.DFS()

Complexity Analysis for DFS:

Time complexity: We need to traverse the whole graph while implementing DFS. therefore, its time complexity is O(V + E).

Space complexity: The algorithm makes use of an extra array. Therefore, in the worst case, the space complexity is O(V).

Applications of DFS:

Finding the number of connected components in a disconnected graph
Detecting a cycle in a graph
Finding all the articulation points in a graph
Finding whether a graph is biconnected or not
For finding strongly connected components in a graph
To find bridges in a graph
For topological sorting
To solve puzzles with only one solution (Eg- mazes)

Conclusion:

In this article, we have gone through the depth first traversal for graphs. We have seen how Depth First Search works for connected as well as disconnected graphs.

We have also seen how DFS works for undirected as well as directed graphs. We have worked upon the implementation of the DFS algorithm in various programming languages and have also seen the practical applications of DFS.

Depth First Search in Data Structure

What is DFS:

Algorithm:

Working of DFS in an Undirected Connected Graph:

DFS on a Directed Graph:

Implementation of DFS in C:

Implementation of DFS in C++

DFS Implementation in Java:

Implementation of DFS in Python:

Handling Disconnected graphs:

Algorithm:

DFS on an Undirected, Disconnected graph:

Implementation for Disconnected graph in C++

Implementation for Disconnected graph in Java:

DFS Implementation for Disconnected graph in Python:

Complexity Analysis for DFS:

Applications of DFS:

Conclusion:

Data Science Tutorials

Programming Tutorials

Trending Tutorials