Depth First Search In a Graph

Depth-First Search (DFS) is a fundamental algorithm used in graph theory and computer science to explore and traverse a graph or a tree-like data structure. The basic idea behind DFS is to start at a particular node (the root or starting node) and then explore as far as possible along each branch before coming back and trying out other paths. This process continues until all the reachable nodes have been visited or the desired node has been found.

DFS prioritizes exploring the depth of the graph before breadth, visiting all the nodes in a particular branch before moving to the next branch. Hence the name “Depth First Search”.

The recursive and iterative DFS implementations mentioned in this article visits/traverses all nodes present in a given graph. If you need to find for a specific value, you can stop the Depth first search immediately after coming across the desired node.

Recursive Implementation

Below is the algorithm for performing Depth first search on a graph using recursion technique:

First we start at a given node or root of the graph/tree for which we need to perform Depth First Search, and then:

Print the current Node.
Mark the current node as visited.
For each unvisited neighbor of the current node: a. Recursively call the DFS function on that neighbor.
Once all neighbors have been visited, backtrack to the previous node and continue with DFS for all other unvisited neighbors.

We need to perform the above algorithm for each node present in the graph so that we do not miss any nodes which are not connected to some other nodes. Below is the implementation of recursive DFS algorithm:


def dfs_recursive(current_node, graph, visited):
  """
  Function to recursively perform a Depth First Search (DFS)
  starting from the current_node.
  
  Args:
  current_node: The node from which DFS starts.
  graph: The graph represented as an adjacency list.
  visited: A set to keep track of all visited nodes.
  """

  # 1. Print the current node
  print(current_node, end=' ')
  
  # 2. Mark the current node as visited
  visited.add(current_node)
  
  # 3. Iterate through each neighbor of the current node
  for neighbor in graph[current_node]:
    # If the neighbor is not visited yet
    if neighbor not in visited:
      # 3.a Recursively call the DFS function on the neighbor
      dfs_recursive(neighbor, graph, visited)

# Sample graph represented as an adjacency list
graph = {
    'A' : ['B', 'C'],
    'B' : ['A', 'C', 'D'],
    'C' : ['A', 'B', 'E', 'F'],
    'D' : ['B'],
    'E' : ['C'],
    'F' : ['C']
}

# Initialize an empty set to store all visited elements
visited = set()

# Perform dfs_recursive function for each node in the graph
for node in graph:
  if node not in visited:
    # Start DFS at the current node
    dfs_recursive(node, graph, visited)


#include <iostream>
#include <unordered_set>
#include <map>
#include <vector>

using namespace std;

// Function to recursively perform a Depth First Search (DFS)
// starting from the current_node
void dfs_recursive(string current_node, map<string, vector<string>>& graph, unordered_set<string>& visited) {
  // 1. Print the current node
  cout << current_node << " ";

  // 2. Mark the current node as visited
  visited.insert(current_node);

  // 3. Iterate through each neighbor of the current node
  for (const auto& neighbor : graph[current_node]) {
    // If the neighbor is not visited yet
    if (visited.find(neighbor) == visited.end()) {
      // 3.a Recursively call the DFS function on the neighbor
      dfs_recursive(neighbor, graph, visited);
    }
  }
}

int main() {
  // Sample graph represented as an adjacency list
  map<string, vector<string>> graph = {
      {"A", {"B", "C"}},
      {"B", {"A", "C", "D"}},
      {"C", {"A", "B", "E", "F"}},
      {"D", {"B"}},
      {"E", {"C"}},
      {"F", {"C"}}
  };

  // Initialize an empty set to store all visited elements
  unordered_set<string> visited;

  // Perform dfs_recursive function for each node in the graph
  for (const auto& node : graph) {
    if (visited.find(node.first) == visited.end()) {
      // Start DFS at the current node
      dfs_recursive(node.first, graph, visited);
    }
  }

  return 0;
}


/**
 * Function to recursively perform a Depth First Search (DFS)
 * starting from the current_node.
 * 
 * @param {string} currentNode - The node from which DFS starts.
 * @param {Object} graph - The graph represented as an adjacency list.
 * @param {Set} visited - A set to keep track of all visited nodes.
 */
function dfsRecursive(currentNode, graph, visited) {
  // 1. Print the current node
  console.log(currentNode, '');

  // 2. Mark the current node as visited
  visited.add(currentNode);

  // 3. Iterate through each neighbor of the current node
  for (let neighbor of graph[currentNode]) {
    // If the neighbor is not visited yet
    if (!visited.has(neighbor)) {
      // 3.a Recursively call the DFS function on the neighbor
      dfsRecursive(neighbor, graph, visited);
    }
  }
}

// Sample graph represented as an adjacency list
const graph = {
  'A': ['B', 'C'],
  'B': ['A', 'C', 'D'],
  'C': ['A', 'B', 'E', 'F'],
  'D': ['B'],
  'E': ['C'],
  'F': ['C']
};

// Initialize an empty set to store all visited elements
const visited = new Set();

// Perform dfsRecursive function for each node in the graph
for (let node in graph) {
  if (!visited.has(node)) {
    // Start DFS at the current node
    dfsRecursive(node, graph, visited);
  }
}


import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class Main {
  
  // Function to recursively perform a Depth First Search (DFS)
  // starting from the current_node.
  public static void dfs_recursive(String current_node, Map<String, Set<String>> graph, Set<String> visited) {
    // 1. Print the current node
    System.out.print(current_node + " ");
    
    // 2. Mark the current node as visited
    visited.add(current_node);
    
    // 3. Iterate through each neighbor of the current node
    for (String neighbor : graph.get(current_node)) {
      // If the neighbor is not visited yet
      if (!visited.contains(neighbor)) {
        // 3.a Recursively call the DFS function on the neighbor
        dfs_recursive(neighbor, graph, visited);
      }
    }
  }

  public static void main(String[] args) {
    // Sample graph represented as an adjacency list
    Map<String, Set<String>> graph = new HashMap<>();
    graph.put("A", new HashSet<>() {{ add("B"); add("C"); }});
    graph.put("B", new HashSet<>() {{ add("A"); add("C"); add("D"); }});
    graph.put("C", new HashSet<>() {{ add("A"); add("B"); add("E"); add("F"); }});
    graph.put("D", new HashSet<>() {{ add("B"); }});
    graph.put("E", new HashSet<>() {{ add("C"); }});
    graph.put("F", new HashSet<>() {{ add("C"); }});

    // Initialize an empty set to store all visited elements
    Set<String> visited = new HashSet<>();

    // Perform dfs_recursive function for each node in the graph
    for (String node : graph.keySet()) {
      if (!visited.contains(node)) {
        // Start DFS at the current node
        dfs_recursive(node, graph, visited);
      }
    }
  }
}

Iterative Implementation

In the recursive DFS approach, the algorithm uses function calls to keep track of the search path, with the system call stack managing the order of exploration. Each recursive call represents a step deeper into the graph, and the algorithm backtracks by returning from the function calls.

On the other hand, the iterative DFS implementation uses an explicit stack data structure to manage the search process. Instead of relying on the system call stack, the algorithm pushes the vertices onto the stack and pops them off as it explores the graph.

One key benefit of the iterative approach is that it can handle larger and deeper graphs more efficiently, as it avoids the potential for stack overflow errors that can occur in the recursive implementation. Additionally, the iterative version can be more easily parallelized, as the stack can be divided and processed concurrently by multiple threads or processes.

Below is the algorithm for performing depth first search using iterative approach:

Start with the root node of the graph or tree.
Push the root node onto a stack.
While the stack is not empty:
- Pop a node from the stack.
- Visit and process the popped node.
- Push all the unvisited neighbors of the popped node onto the stack, in the order they appear in the graph or tree.
Repeat steps 3 until the stack is empty.

Below is the implementation of the iterative DFS algorithm:


def dfs_iterative(start_node, graph, visited):
  """
  Function to iteratively perform a Depth First Search (DFS)
  starting from the current_node.
  
  Args:
  start_node: The node from which DFS starts.
  graph: The graph represented as an adjacency list.
  visited: A set to keep track of all visited nodes.
  """

  # Create a stack to store the nodes to visit
  stack = [start_node]
  
  # While the stack is not empty
  while stack:
    # Pop a node from the stack
    current_node = stack.pop()
    
    if current_node not in visited:
      # Process/Print the current node
      print(current_node, end=' ')
      
      # Mark the current node as visited
      visited.add(current_node)
    
      # Push all the unvisited neighbors of the current node onto the stack
      for neighbor in reversed(graph[current_node]):
        if neighbor not in visited:
          stack.append(neighbor)

# Sample graph represented as an adjacency list
graph = {
    'A' : ['B', 'C'],
    'B' : ['A', 'C', 'D'],
    'C' : ['A', 'B', 'E', 'F'],
    'D' : ['B'],
    'E' : ['C'],
    'F' : ['C']
}

# Initialize an empty set to store all visited elements
visited = set()

# Perform dfs_iterative function for each node in the graph
for node in graph:
  if node not in visited:
    # Start DFS at the current node
    dfs_iterative(node, graph, visited)


#include <iostream>
#include <unordered_set>
#include <stack>
#include <map>
#include <vector>

using namespace std;

// Function to iteratively perform a Depth First Search (DFS)
// starting from the current_node.
void dfs_iterative(string start_node, map<string, vector<string>>& graph, unordered_set<string>& visited) {
  // Create a stack to store the nodes to visit
  stack<string> stack_nodes;
  stack_nodes.push(start_node);

  // While the stack is not empty
  while (!stack_nodes.empty()) {
    // Pop a node from the stack
    string current_node = stack_nodes.top();
    stack_nodes.pop();

    // If the current node is not visited
    if (visited.find(current_node) == visited.end()) {
      // Process/Print the current node
      cout << current_node << " ";

      // Mark the current node as visited
      visited.insert(current_node);

      // Push all the unvisited neighbors of the current node onto the stack
      for (auto neighbor = graph[current_node].rbegin(); neighbor != graph[current_node].rend(); ++neighbor) {
        if (visited.find(*neighbor) == visited.end()) {
          stack_nodes.push(*neighbor);
        }
      }
    }
  }
}

int main() {
  // Sample graph represented as an adjacency list
  map<string, vector<string>> graph = {
      {"A", {"B", "C"}},
      {"B", {"A", "C", "D"}},
      {"C", {"A", "B", "E", "F"}},
      {"D", {"B"}},
      {"E", {"C"}},
      {"F", {"C"}}
  };

  // Initialize an empty set to store all visited elements
  unordered_set<string> visited;

  // Perform dfs_iterative function for each node in the graph
  for (auto node : graph) {
    if (visited.find(node.first) == visited.end()) {
      // Start DFS at the current node
      dfs_iterative(node.first, graph, visited);
    }
  }

  return 0;
}


/**
 * Function to iteratively perform a Depth First Search (DFS)
 * starting from the current_node.
 * 
 * @param {string} startNode - The node from which DFS starts.
 * @param {Object} graph - The graph represented as an adjacency list.
 * @param {Set} visited - A set to keep track of all visited nodes.
 */
function dfsIterative(startNode, graph, visited) {
  // Create a stack to store the nodes to visit
  const stack = [startNode];

  // While the stack is not empty
  while (stack.length > 0) {
    // Pop a node from the stack
    const currentNode = stack.pop();

    if (!visited.has(currentNode)) {
      // Process/Print the current node
      console.log(currentNode);

      // Mark the current node as visited
      visited.add(currentNode);

      // Push all the unvisited neighbors of the current node onto the stack
      for (let i = graph[currentNode].length - 1; i >= 0; i--) {
        const neighbor = graph[currentNode][i];
        if (!visited.has(neighbor)) {
          stack.push(neighbor);
        }
      }
    }
  }
}

// Sample graph represented as an adjacency list
const graph = {
  'A': ['B', 'C'],
  'B': ['A', 'C', 'D'],
  'C': ['A', 'B', 'E', 'F'],
  'D': ['B'],
  'E': ['C'],
  'F': ['C']
};

// Initialize an empty set to store all visited elements
const visited = new Set();

// Perform dfsIterative function for each node in the graph
for (const node in graph) {
  if (!visited.has(node)) {
    // Start DFS at the current node
    dfsIterative(node, graph, visited);
  }
}


import java.util.*;

public class Main {
  public static void dfsIterative(String startNode, Map<String, List<String>> graph, Set<String> visited) {
    // Create a stack to store the nodes to visit
    Stack<String> stack = new Stack<>();
    stack.push(startNode);

    // While the stack is not empty
    while (!stack.isEmpty()) {
      // Pop a node from the stack
      String currentNode = stack.pop();

      if (!visited.contains(currentNode)) {
        // Process/Print the current node
        System.out.print(currentNode + " ");

        // Mark the current node as visited
        visited.add(currentNode);

        // Push all the unvisited neighbors of the current node onto the stack
        List<String> neighbors = graph.get(currentNode);
        for (int i = neighbors.size() - 1; i >= 0; i--) {
          String neighbor = neighbors.get(i);
          if (!visited.contains(neighbor)) {
            stack.push(neighbor);
          }
        }
      }
    }
  }

  public static void main(String[] args) {
    // Sample graph represented as an adjacency list
    Map<String, List<String>> graph = new HashMap<>();
    graph.put("A", Arrays.asList("B", "C"));
    graph.put("B", Arrays.asList("A", "C", "D"));
    graph.put("C", Arrays.asList("A", "B", "E", "F"));
    graph.put("D", Arrays.asList("B"));
    graph.put("E", Arrays.asList("C"));
    graph.put("F", Arrays.asList("C"));

    // Initialize an empty set to store all visited elements
    Set<String> visited = new HashSet<>();

    // Perform dfsIterative function for each node in the graph
    for (String node : graph.keySet()) {
      if (!visited.contains(node)) {
        // Start DFS at the current node
        dfsIterative(node, graph, visited);
      }
    }
  }
}

Time and Space Complexity

Time Complexity:

The time complexity of DFS depends on the number of vertices (V) and edges (E) in the graph. In the worst case, DFS visits all the vertices and edges in the graph, resulting in a time complexity of O(V + E).

This means that the time taken to perform DFS grows linearly with the size of the graph, as the algorithm needs to visit each vertex and edge at most once.

Space Complexity:

In addition to the space used to store the graph as adjacency list or matrix, additional space is required by function call stack in recursive implementation and custom stack used in iterative implementation. This additional space complexity is O(H), where (H) is the maximum depth of the recursion. It’s maximum value can go up to the total number of vertices in the graph.

Use Cases of Depth First Search

Topological Sorting: DFS is useful for determining the topological order of a directed acyclic graph (DAG). This is particularly beneficial in scenarios such as task scheduling and resolving dependencies where some tasks must be completed before others.
Cycle Detection: DFS can be employed to detect cycles in a graph. This is crucial in applications like compiler design, where cycles can indicate issues in code dependencies, or in network routing, where cycles might cause inefficiencies or routing loops.
Graph Traversal: DFS can traverse all the nodes in a graph, visiting nodes by diving deep into each branch before backtracking, which can be useful for exploring hierarchical structures or game trees.
Connected Components: In undirected graphs, DFS can be used to easily find all the connected components, which is essential in clustering applications and network analysis.