Depth-First Search (DFS) 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.

O(V)

Explanation: 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.