Depth-First Search (DFS) in Graphs

Problem Statement❯

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.

Examples❯

Input Graph (Adjacency List)	DFS Output (Starting from smallest node)	Description
{1: [2, 3], 2: [1, 4, 5], 3: [1], 4: [2], 5: [2]}	1 → 2 → 4 → 5 → 3	Classic DFS tree with backtracking: visits 2 → 4 → 5, then backtracks to visit 3.
{1: [2, 3], 2: [1, 4], 3: [1, 5], 4: [2], 5: [3, 6], 6: [5]}	1 → 2 → 4 → 3 → 5 → 6	DFS explores left from 1 to 2 → 4, backtracks to 3 → 5 → 6. Deep tree with branching.
{1: [2, 3], 2: [1, 3, 4], 3: [1, 2], 4: [2, 5], 5: [4]}	1 → 2 → 3 → 4 → 5	Cycle between 1-2-3 handled properly; DFS continues deeper through node 4 to 5.
{1: [2], 2: [1, 3, 4], 3: [2], 4: [2, 5, 6], 5: [4], 6: [4]}	1 → 2 → 3 → 4 → 5 → 6	DFS covers a “Y”-shaped graph with multiple forks under node 4.
{0: [1], 1: [0, 2], 2: [1, 3], 3: [2, 4], 4: [3]}	0 → 1 → 2 → 3 → 4	Linear path graph; DFS proceeds from left to right in straight line without backtracking.

Solution❯

What is DFS and When Is It Used?

Depth-First Search (DFS) is a graph traversal algorithm that starts from a source node and explores as far as possible along each branch before backtracking. It is commonly used for problems like connectivity checks, cycle detection, and solving puzzles such as mazes.

How DFS Works

When DFS is started from a node, it marks that node as visited and recursively (or using a stack) visits each of its unvisited neighbors. This continues until all possible paths from the starting node are fully explored.

Case 1: Fully Connected Graph

In a graph where every node is connected (directly or indirectly), DFS will eventually visit every node. This helps identify all components reachable from the source.

Case 2: Disconnected Graph

If the graph is disconnected, DFS from one node will not reach nodes in other disconnected components. To traverse all nodes in such cases, DFS should be applied to every unvisited node in the graph (often used in counting connected components).

Case 3: Graph with Cycles

DFS can handle cycles using a visited set to avoid infinite loops. If a visited node is encountered again, DFS simply skips it.

Case 4: Directed vs. Undirected Graphs

DFS works similarly for both, but the direction of edges is respected. In a directed graph, DFS follows edges only in the given direction. In undirected graphs, it can traverse both directions.

Implementation Insight

DFS can be implemented recursively or using an explicit stack (for iterative approach). Both approaches use a visited structure (set or array) to track explored nodes.

Algorithm Steps❯

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

Code

JavaScript

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)); // Output: [0, 1, 3, 2]

Time Complexity❯

Case	Time Complexity	Explanation
Best Case	O(V + E)	DFS visits each node and edge once, even in the best case where traversal may end early due to no unvisited neighbors.
Average Case	O(V + E)	Each node is explored once and each edge is checked once, regardless of the structure of the graph.
Worst Case	O(V + E)	In the worst case, DFS explores all vertices and all edges, particularly in a densely connected graph.

Space Complexity❯

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.

⬅ Previous TopicBreadth-First Search in Graphs

Next Topic ⮕Number of Provinces in an Undirected Graph