Depth First Search (DFS) in Data Structure

In the last article, we learned about graphs in data structures. Graphs are one of the efficient ways that are used to model daily life problems and find an optimal solution. In this article, we will learn about traversing techniques for the graph and their implementation

Depth First Search

DFS is a recursive traversal algorithm for searching all the vertices of a graph or tree data structure. It starts from the first node of graph G and then goes to further vertices until the goal vertex is reached.

• DFS uses stack as its backend data structure
• edges that lead to an unvisited node are called discovery edges while the edges that lead to an already visited node are called block edges.

DFS procedure

DFS implementation categorizes the vertices in the graphs into two categories:

• Visited
• Not visited

The major objective is to visit each node and keep marking them as “visited” without making any cycle.

Steps for DFS algorithms:

1. Start by pushing starting vertex of the graph into the stack
2. Pop the top item of the stack and add it to the visited list
3. Create the adjacency list for that vertex. Add the non-visited nodes in the list to the top of the stack
4. Keep repeating steps 2 and 3 until the stack is empty

Depth First Search Algorithm

• Step 1: STATUS = 1 for each node in Graph G
• Step 2: Push the starting node A in the stack. set its STATUS = 2
• Step 3: Repeat Steps 4 and 5 until STACK is empty
• Step 4: Pop the top node N from the stack. Process it and set its STATUS = 3
• Step 5: Push all the neighbors of N with STATUS =1 into the stack and set their STATUS = 2
  [END OF LOOP]
• Step 6: stop

Working of Depth First Search

Let us consider the graph below:

Starting node: A

Step 1: Create an adjacency list for the above graph.

Step 2: Create an empty stack.

Step 3: Push ‘A’ into the stack

Step 4: Pop ‘A’ and push ‘B’ and ‘F’. Mark node ‘A’ as the visited node

Step 5: pop ‘F’ and push ‘D’. Mark ‘F’ as a visited node.

Step 6: pop ‘D’ and push ‘C’. Mark ‘D’ as a visited node.

Step 7: pop ‘C’ and push ‘E’. Mark ‘C’ as a visited node.

Step 8: pop ‘E’. Mark ‘E’ as a visited node. No new node is left.

Step 9: pop ‘B’. Mark ‘B’ as visited. All the nodes in the graph are visited now.

DFS implementation in C

#include <stdio.h>
#include <stdlib.h>

struct node 
{
  int vertex;
  struct node* next;
};

struct node* createNode(int v);

struct Graph 
{
  int numVertices;
  int* visited;

  struct node** adjLists;
};

void DFS(struct Graph* graph, int vertex) 
{
  struct node* adjList = graph->adjLists[vertex];
  struct node* temp = adjList;

  graph->visited[vertex] = 1;
  printf("Visited %d \n", vertex);

  while (temp != NULL) 
  {
    int connected_Vertex = temp->vertex;

    if (graph->visited[connected_Vertex] == 0) 
    {
      DFS(graph, connected_Vertex);
    }
    temp = temp->next;
  }
}

struct node* createNode(int vert) 
{
  struct node* newNode = malloc(sizeof(struct node));
  newNode->vertex = vert;
  newNode->next = NULL;
  return newNode;
}

struct Graph* createGraph(int vertices) 
{
  struct Graph* graph = malloc(sizeof(struct Graph));
  graph->numVertices = vertices;

  graph->adjLists = malloc(vertices * sizeof(struct node*));

  graph->visited = malloc(vertices * sizeof(int));

  int i;
  
  for (i = 0; i < vertices; i++) 
  {
    graph->adjLists[i] = NULL;
    graph->visited[i] = 0;
  }
  return graph;
}

void addEdge(struct Graph* graph, int src, int dest) 
{
  struct node* newNode = createNode(dest);
  newNode->next = graph->adjLists[src];
  graph->adjLists[src] = newNode;

  newNode = createNode(src);
  newNode->next = graph->adjLists[dest];
  graph->adjLists[dest] = newNode;
}

void printDFS(struct Graph* graph) 
{
  int v;
  for (v = 0; v < graph->numVertices; v++) 
  {
    struct node* temp = graph->adjLists[v];
    printf("\nvertex %d\ : ", v);
    while (temp) {
      printf("%d -> ", temp->vertex);
      temp = temp->next;
    }
    printf("\n");
  }
}

int main() 
{
  struct Graph* graph = createGraph(5);
  addEdge(graph, 0, 1);
  addEdge(graph, 0, 2);
  addEdge(graph, 0, 3);
  addEdge(graph, 1, 4);
  addEdge(graph, 2, 3);

  printDFS(graph);

  DFS(graph, 0);

  return 0;
}

DFS implementation in C++

#include <iostream>
#include <list>
using namespace std;

class DSGraph 
{
  int numVertices;
  list<int> *adjLists;
  bool *visited;

   public:
  DSGraph(int V);
  void addEdge(int src, int dest);
  void DFS(int vertex);
};

DSGraph::DSGraph(int vert) 
{
  numVertices = vert;
  adjLists = new list<int>[vert];
  visited = new bool[vert];
}

void DSGraph::addEdge(int S_node, int D_node) 
{
  adjLists[S_node].push_front(D_node);
}

void DSGraph::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() {
  DSGraph g(5);
  g.addEdge(0, 1);
  g.addEdge(0, 2);
  g.addEdge(0, 3);
  g.addEdge(1, 4);
  g.addEdge(2, 3);

  g.DFS(3);

  return 0;
}

Implementation of Depth First Search in JAVA

import java.util.*;

public class Graph 
{
  private LinkedList<Integer> adjLists[];
  private boolean visited[];

  Graph(int vert) 
  {
    adjLists = new LinkedList[vert];
    visited = new boolean[vert];

    for (int i = 0; i < vert; i++)
      adjLists[i] = new LinkedList<Integer>();
  }

  void addEdge(int S_node, int D_node) 
  {
    adjLists[S_node].add(D_node);
  }

  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(5);

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

    System.out.println("DFS");

    g.DFS(2);
  }
}

DFS implementation in Python

graph = {
    'A' : ['B','C','D'],
    'B' : ['E'],
    'C' : ['D'],
    'D' : ['C'],
    'E' : ['C']
   }

visited = set() 

def dfs(visited, graph, node):
    if node not in visited:
        print (node)
        visited.add(node)
        for neighbour in graph[node]:
            dfs(visited, graph, neighbour)

dfs(visited, graph, 'A')

Depth First Search Complexity

The time complexity of DFS is represented in the form O(V+E) where V is the number of vertices and E is the number of edges.

The space complexity of DFS algorithms is O(V).

Disconnected graph in DFS

It might be possible that all the vertices are not reachable from the starting vertex in the case of a disconnected graph. For complete DFS traversal, Run DFS traversal from all unvisited nodes after the connected graph is completely visited.

Procedure

1. Create a recursive function that takes the index of the node and a visited array as the input.
2. Mark the current node as a visited node.
3. Traverse all the adjacent and unmarked nodes
4. Run a loop from 0 to the number of nodes and check if the node is unvisited. If yes, call the recursive function with the index of the unvisited node.

Handling disconnected graph in C++

#include <iostream>
#include <list>
using namespace std;

class DSGraph 
{
  int numVertices;
  list<int> *adjLists;
  bool *visited;

   public:
 map<int, bool> visited;
    map<int, list<int>> adj;
  DSGraph(int V);
  void addEdge(int src, int dest);
  void DFS(int vertex);
};

DSGraph::DSGraph(int vert) 
{
  numVertices = vert;
  adjLists = new list<int>[vert];
  visited = new bool[vert];
}

void DSGraph::addEdge(int S_node, int D_node) 
{
  adjLists[S_node].push_front(D_node);
}

void DSGraph::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);

  for (auto i:adj)
        if (visited[i.first] == false)
            DFSUtil(i.first);

}

int main() {
  DSGraph g(5);
  g.addEdge(0, 1);
  g.addEdge(0, 2);
  g.addEdge(0, 3);
  g.addEdge(1, 4);
  g.addEdge(2, 3);

  g.DFS(3);

  return 0;
}

Handling disconnected graph in JAVA

import java.util.*;

public class Graph 
{
  private LinkedList<Integer> adjLists[];
  private boolean visited[];

  Graph(int vert) 
  {
    adjLists = new LinkedList[vert];
    visited = new boolean[vert];

    for (int i = 0; i < vert; i++)
      adjLists[i] = new LinkedList<Integer>();
  }

  void addEdge(int S_node, int D_node) 
  {
    adjLists[S_node].add(D_node);
  }

  void DFS(int vertex) 
  {
    Boolean visited[] =new boolean[4]
    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);
for (int i = 0; i < V; ++i)
            if (visited[i] == false)
                DFS(visited);

    }
  }

  public static void main(String args[]) 
  {
    Graph g = new Graph(5);

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

    System.out.println("DFS");

    g.DFS(2);
  }
}

DFS implementation in Python

graph = {
    'A' : ['B','C','D'],
    'B' : ['E'],
    'C' : ['D'],
    'D' : ['C'],
    'E' : ['C']
   }

visited = set() 

def dfs(visited, graph, node):
    if node not in visited:
        print (node)
        visited.add(node)
        for neighbour in graph[node]:
            dfs(visited, graph, neighbour)
        for vertex in list(self.graph):
            if vertex not in visited:
                self.dfs(vertex, graph, node)


dfs(visited, graph, 'A')

Applications of Depth First Search

1. Solving maze like puzzles with only one solution
2. Dfs is highly preferred approach for solving problem like, job scheduling, data serialization, etc using topological sorting
3. Network analysis and mapping routes
4. Detection of cycle in graphs

Conclusion

DFS is the traversal algorithms for graphs and trees. In this article, we witnessed the DFS algorithm, its working, and its implementation in different programming languages. In the next article, we will learn about another graph traversal algorithm BFS ( Breadth-First Search ).