Depth-First Search in Graphs

Depth-First Search (DFS) is a popular graph traversal technique that explores as far along a branch as possible before backtracking. Starting from a node, DFS goes deep into the graph, exploring child nodes before sibling nodes.

DFS is useful for tasks like detecting cycles, pathfinding, topological sorting, and solving puzzles with backtracking.

Understanding the Problem

We are given a graph with a set of nodes and edges. The task is to traverse the graph using the Depth-First Search (DFS) algorithm. DFS explores as far as possible along each branch before backtracking, ensuring that each node is visited once.

This traversal technique is foundational for many graph problems like counting connected components, detecting cycles, and solving maze-like puzzles. In this lesson, we will understand how DFS works step-by-step and apply it to a practical example with beginner-friendly explanations.

Step-by-Step Solution with Example

Step 1: Define the Graph

Let's take a sample undirected graph represented as an adjacency list:

{
  0: [1, 2],
  1: [0, 3],
  2: [0],
  3: [1, 4],
  4: [3]
}

This graph has 5 nodes. The connections (edges) between nodes are undirected, meaning you can go both ways along the edge. For example, 0 is connected to 1 and 2, and 1 is connected back to 0 and to 3.

Step 2: Understand the DFS Approach

DFS starts at a node (say, node 0), marks it as visited, and then recursively explores each unvisited neighbor. Once all neighbors are visited, it backtracks.

We use a visited array or set to keep track of nodes we have already seen, to avoid visiting the same node again and getting stuck in cycles.

Step 3: Implement the DFS Logic

Here’s a basic recursive DFS implementation:

function dfs(node, visited, graph) {
  visited[node] = true;
  console.log("Visited", node);
  for (let neighbor of graph[node]) {
    if (!visited[neighbor]) {
      dfs(neighbor, visited, graph);
    }
  }
}

Step 4: Apply DFS to the Graph

We start from node 0 and visit its neighbors one by one. Here's how it works:

1. Visit node 0 ➝ mark as visited
2. From 0, go to node 1 ➝ mark 1 visited
3. From 1, go to node 3 ➝ mark 3 visited
4. From 3, go to node 4 ➝ mark 4 visited
5. Backtrack to 3 ➝ 1 ➝ 0
6. From 0, go to node 2 ➝ mark 2 visited

All nodes are now visited.

Step 5: Visualize the Order

The order of traversal will be: 0 → 1 → 3 → 4 → 2

Edge Cases

Disconnected Graph

If the graph is disconnected (e.g., two separate subgraphs), starting DFS from one node will not visit all nodes. In such cases, we run DFS for every unvisited node in a loop:

for (let node in graph) {
  if (!visited[node]) {
    dfs(node, visited, graph);
  }
}

Graph with Cycles

If a graph contains cycles, DFS can fall into infinite loops without a visited check. That’s why we always verify whether a node has already been visited before calling DFS on it.

Directed Graphs

DFS logic remains the same, but it follows the direction of edges. That means if there's an edge from A → B, DFS can go from A to B, but not from B to A unless a separate edge exists.

Empty Graph

If the graph has no nodes or edges, the DFS simply ends immediately with no output. Always validate inputs before running DFS logic.

Finally

Depth-First Search is a powerful tool to explore and analyze graphs. Understanding the traversal order and marking visited nodes are the key steps to avoid infinite loops and ensure correctness. For disconnected graphs or graphs with cycles, we slightly extend the basic DFS to handle all components safely.

As you practice, try applying DFS to real-world scenarios like social networks (friend groups), map navigation (paths and roads), and puzzle solving (mazes). This will strengthen your intuition and mastery over graph traversal techniques.

1. Initialize a visited set.
2. Start DFS from the given node.
3. Mark the current node as visited and process it.
4. Recursively (or using a stack) visit all unvisited neighbors.
5. Repeat until all connected nodes have been visited.

#include <stdio.h>
#define MAX 100

int graph[MAX][MAX];
int visited[MAX];
int n;

void dfs(int node) {
  if (visited[node]) return;
  visited[node] = 1;
  printf("%d ", node);

  for (int i = 0; i < n; i++) {
    if (graph[node][i] && !visited[i]) {
      dfs(i);
    }
  }
}

int main() {
  n = 4;
  graph[0][1] = graph[1][0] = 1;
  graph[0][2] = graph[2][0] = 1;
  graph[1][3] = graph[3][1] = 1;

  printf("DFS from node 0: ");
  dfs(0);
  return 0;
}

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

void dfs(int node, vector<vector<int>>& graph, vector<bool>& visited) {
  if (visited[node]) return;
  visited[node] = true;
  cout << node << " ";

  for (int neighbor : graph[node]) {
    if (!visited[neighbor]) {
      dfs(neighbor, graph, visited);
    }
  }
}

int main() {
  vector<vector<int>> graph = {
    {1, 2}, {0, 3}, {0}, {1}
  };
  vector<bool> visited(4, false);

  cout << "DFS from node 0: ";
  dfs(0, graph, visited);
  return 0;
}

def dfs(graph, node, visited=None, result=None):
    if visited is None:
        visited = set()
    if result is None:
        result = []

    if node in visited:
        return

    visited.add(node)
    result.append(node)

    for neighbor in graph.get(node, []):
        if neighbor not in visited:
            dfs(graph, neighbor, visited, result)
    return result

graph = {
    0: [1, 2],
    1: [0, 3],
    2: [0],
    3: [1]
}

print("DFS from node 0:", dfs(graph, 0))

import java.util.*;

public class DFSGraph {
  public static void dfs(Map<Integer, List<Integer>> graph, int node, Set<Integer> visited, List<Integer> result) {
    if (visited.contains(node)) return;
    visited.add(node);
    result.add(node);
    for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
      if (!visited.contains(neighbor)) {
        dfs(graph, neighbor, visited, result);
      }
    }
  }

  public static void main(String[] args) {
    Map<Integer, List<Integer>> graph = new HashMap<>();
    graph.put(0, Arrays.asList(1, 2));
    graph.put(1, Arrays.asList(0, 3));
    graph.put(2, Arrays.asList(0));
    graph.put(3, Arrays.asList(1));

    Set<Integer> visited = new HashSet<>();
    List<Integer> result = new ArrayList<>();

    dfs(graph, 0, visited, result);
    System.out.println("DFS from node 0: " + result);
  }
}

function dfs(graph, start, visited = new Set(), result = []) {
  if (visited.has(start)) return;
  visited.add(start);
  result.push(start);

  for (const neighbor of graph[start] || []) {
    if (!visited.has(neighbor)) {
      dfs(graph, neighbor, visited, result);
    }
  }
  return result;
}

const graph = {
  0: [1, 2],
  1: [0, 3],
  2: [0],
  3: [1]
};

console.log("DFS from node 0:", dfs(graph, 0));

package main

import (
  "fmt"
)

func dfs(graph map[int][]int, node int, visited map[int]bool, result *[]int) {
  if visited[node] {
    return
  }
  visited[node] = true
  *result = append(*result, node)

  for _, neighbor := range graph[node] {
    if !visited[neighbor] {
      dfs(graph, neighbor, visited, result)
    }
  }
}

func main() {
  graph := map[int][]int{
    0: {1, 2},
    1: {0, 3},
    2: {0},
    3: {1},
  }
  visited := make(map[int]bool)
  result := []int{}
  dfs(graph, 0, visited, &result)
  fmt.Println("DFS from node 0:", result)
}

use std::collections::{HashMap, HashSet};

fn dfs(node: i32, graph: &HashMap<i32, Vec<i32>>, visited: &mut HashSet<i32>, result: &mut Vec<i32>) {
  if visited.contains(&node) {
    return;
  }
  visited.insert(node);
  result.push(node);
  for &neighbor in graph.get(&node).unwrap_or(&vec![]) {
    if !visited.contains(&neighbor) {
      dfs(neighbor, graph, visited, result);
    }
  }
}

fn main() {
  let graph: HashMap<i32, Vec<i32>> = [
    (0, vec![1, 2]),
    (1, vec![0, 3]),
    (2, vec![0]),
    (3, vec![1]),
  ].iter().cloned().collect();

  let mut visited = HashSet::new();
  let mut result = vec![];

  dfs(0, &graph, &mut visited, &mut result);
  println!("DFS from node 0: {:?}", result);
}

fun dfs(
  graph: Map<Int, List<Int>>,
  node: Int,
  visited: MutableSet<Int>,
  result: MutableList<Int>
) {
  if (visited.contains(node)) return
  visited.add(node)
  result.add(node)
  for (neighbor in graph[node].orEmpty()) {
    if (!visited.contains(neighbor)) {
      dfs(graph, neighbor, visited, result)
    }
  }
}

fun main() {
  val graph = mapOf(
    0 to listOf(1, 2),
    1 to listOf(0, 3),
    2 to listOf(0),
    3 to listOf(1)
  )
  val visited = mutableSetOf<Int>()
  val result = mutableListOf<Int>()
  dfs(graph, 0, visited, result)
  println("DFS from node 0: $result")
}

import Foundation

func dfs(_ graph: [Int: [Int]], _ node: Int, _ visited: inout Set<Int>, _ result: inout [Int]) {
  if visited.contains(node) { return }
  visited.insert(node)
  result.append(node)

  for neighbor in graph[node] ?? [] {
    if !visited.contains(neighbor) {
      dfs(graph, neighbor, &visited, &result)
    }
  }
}

let graph: [Int: [Int]] = [
  0: [1, 2],
  1: [0, 3],
  2: [0],
  3: [1]
]

var visited = Set<Int>()
var result = [Int]()
dfs(graph, 0, &visited, &result)
print("DFS from node 0:", result)

function dfs(
  graph: Record<number, number[]>,
  node: number,
  visited = new Set<number>(),
  result: number[] = []
): number[] {
  if (visited.has(node)) return result;
  visited.add(node);
  result.push(node);

  for (const neighbor of graph[node] || []) {
    if (!visited.has(neighbor)) {
      dfs(graph, neighbor, visited, result);
    }
  }
  return result;
}

const graph: Record<number, number[]> = {
  0: [1, 2],
  1: [0, 3],
  2: [0],
  3: [1],
};

console.log("DFS from node 0:", dfs(graph, 0));

Time complexity

Space complexity

O(V)

The space used is proportional to the number of vertices due to the visited set and the recursion stack or explicit stack used in the process.