DFS Depth First Search on Graph in DSA Javascript

Mental Model

DFS explores as far as possible along each branch before backtracking. It dives deep into one path before trying others.

Analogy: Imagine exploring a maze by always taking the first unexplored path you see, going deep until you hit a dead end, then backtracking to try other paths.

Graph adjacency list:
0 -> [1, 2]
1 -> [2]
2 -> [0, 3]
3 -> [3]
Start at node 2 ↑

Dry Run Walkthrough

Input: Graph: 0->1,0->2,1->2,2->0,2->3,3->3; start DFS at node 2

Goal: Visit all nodes reachable from node 2 using DFS order

Step 1: Start DFS at node 2, mark 2 visited

Visited: {2}
Stack: [2]

Why: We begin exploring from node 2

Step 2: From node 2, visit neighbor 0, mark 0 visited

Visited: {2, 0}
Stack: [2, 0]

Why: Go deep to first neighbor of 2

Step 3: From node 0, visit neighbor 1, mark 1 visited

Visited: {2, 0, 1}
Stack: [2, 0, 1]

Why: Continue deep exploration from 0

Step 4: From node 1, visit neighbor 2 but 2 already visited, backtrack

Visited: {2, 0, 1}
Stack: [2, 0]

Why: Avoid revisiting nodes to prevent loops

Step 5: Back at node 0, next neighbor 2 already visited, backtrack

Visited: {2, 0, 1}
Stack: [2]

Why: All neighbors of 0 explored

Step 6: From node 2, visit neighbor 3, mark 3 visited

Visited: {2, 0, 1, 3}
Stack: [2, 3]

Why: Explore next neighbor of 2

Step 7: From node 3, visit neighbor 3 but already visited, backtrack

Visited: {2, 0, 1, 3}
Stack: [2]

Why: Avoid infinite loop on self-loop

Step 8: Back at node 2, all neighbors visited, DFS complete

Visited: {2, 0, 1, 3}
Stack: []

Why: All reachable nodes explored

Result:

Visited nodes in DFS order: 2 -> 0 -> 1 -> 3

Annotated Code

DSA Javascript

class Graph {
  constructor(vertices) {
    this.vertices = vertices;
    this.adjList = new Map();
    for (let i = 0; i < vertices; i++) {
      this.adjList.set(i, []);
    }
  }

  addEdge(v, w) {
    this.adjList.get(v).push(w);
  }

  dfs(start) {
    const visited = new Set();
    const result = [];

    const dfsVisit = (vertex) => {
      visited.add(vertex); // mark current node visited
      result.push(vertex); // record visit order
      for (const neighbor of this.adjList.get(vertex)) {
        if (!visited.has(neighbor)) {
          dfsVisit(neighbor); // recursively visit neighbors
        }
      }
    };

    dfsVisit(start);
    return result;
  }
}

// Driver code
const g = new Graph(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);

const dfsResult = g.dfs(2);
console.log(dfsResult.join(' -> '));

visited.add(vertex); // mark current node visited

mark current node as visited to avoid revisiting

result.push(vertex); // record visit order

record the order of node visits

for (const neighbor of this.adjList.get(vertex)) {

iterate over all neighbors of current node

if (!visited.has(neighbor)) {

only visit neighbors not visited yet

dfsVisit(neighbor); // recursively visit neighbors

go deeper into neighbor nodes

Output

2 -> 0 -> 1 -> 3

Complexity Analysis

Time: O(V + E) because DFS visits every vertex and edge once

Space: O(V) for the visited set and recursion stack in worst case

vs Alternative: Compared to BFS which uses a queue and explores level by level, DFS uses recursion and explores depth first; both have similar time but different traversal orders

Edge Cases

Graph with no edges

DFS visits only the start node

DSA Javascript

visited.add(vertex); // mark current node visited

Graph with self-loop

DFS visits the node once and avoids infinite loop by checking visited

DSA Javascript

if (!visited.has(neighbor)) {

Disconnected graph, start at isolated node

DFS visits only nodes reachable from start, isolated nodes remain unvisited

DSA Javascript

dfsVisit(start);

When to Use This Pattern

When you need to explore all nodes reachable from a start point deeply before backtracking, use DFS because it naturally follows paths to their end.

Common Mistakes

Mistake: Not marking nodes as visited before recursive calls causing infinite loops
Fix: Mark nodes as visited immediately when first visiting them

Mistake: Visiting neighbors without checking if already visited
Fix: Always check visited set before recursive DFS call

Summary

DFS visits nodes by going deep along each path before backtracking.

Use DFS when you want to explore all paths from a start node deeply.

The key is to mark nodes visited as soon as you see them to avoid loops.

Practice

1. What does DFS (Depth First Search) do when traversing a graph?

easy

A. It only visits nodes connected directly to the start node.

B. It visits nodes level by level from the start node.

C. It explores as far as possible along each branch before backtracking.

D. It randomly visits nodes without any order.

Solution

1. Step 1: Understand DFS traversal

   DFS explores a path deeply before moving to another path.

2. Step 2: Compare with other traversals

   BFS visits nodes level by level, but DFS goes deep first.

3. Final Answer:

   It explores as far as possible along each branch before backtracking. -> Option C

4. Quick Check:

   DFS = deep exploration first [OK]

Hint: DFS goes deep first, BFS goes wide first [OK]

Common Mistakes:

• Confusing DFS with BFS
• Thinking DFS visits nodes randomly
• Assuming DFS only visits direct neighbors

2. Which of the following is the correct way to start a DFS function in JavaScript for a graph represented as adjacency list graph?

easy

A. function dfs(node, visited = new Set()) {

B. function dfs(node, visited = []) {

C. function dfs(node, visited = {}) {

D. function dfs(node, visited = 0) {

Solution

1. Step 1: Identify suitable data structure for visited nodes

   A Set is ideal to track visited nodes efficiently.

2. Step 2: Check function signature correctness

   Using visited = new Set() initializes visited nodes properly.

3. Final Answer:

   function dfs(node, visited = new Set()) { -> Option A

4. Quick Check:

   Use Set for visited nodes [OK]

Hint: Use Set to track visited nodes in DFS [OK]

Common Mistakes:

• Using array or object incorrectly for visited
• Initializing visited as a number
• Not initializing visited parameter

3. Given the graph adjacency list:

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

function dfs(node, visited = new Set()) {
  visited.add(node);
  for (const neighbor of graph[node]) {
    if (!visited.has(neighbor)) {
      dfs(neighbor, visited);
    }
  }
  return Array.from(visited);
}

console.log(dfs(1));

What is the output?

medium

A. [1, 3, 2, 4]

B. [1, 4, 2, 3]

C. [1, 2, 3, 4]

D. [1, 2, 4, 3]

Solution

1. Step 1: Start DFS from node 1

   Visit 1, then neighbors 2 and 3 in order.

2. Step 2: Visit neighbors recursively

   From 2, visit 4. From 3, no neighbors. Order: 1, 2, 4, 3.

3. Final Answer:

   [1, 2, 4, 3] -> Option D

4. Quick Check:

   DFS order = 1,2,4,3 [OK]

Hint: Follow neighbors deeply before next sibling [OK]

Common Mistakes:

• Visiting neighbors in wrong order
• Confusing BFS order with DFS
• Not converting Set to array properly

4. Find the error in this DFS code snippet for graph traversal:

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

function dfs(node, visited = new Set()) {
  visited.add(node);
  for (const neighbor of graph[node]) {
    if (visited.has(neighbor)) {
      dfs(neighbor, visited);
    }
  }
  return visited;
}

console.log(Array.from(dfs(1)));

medium

A. The condition should be if (!visited.has(neighbor)) instead of if (visited.has(neighbor))

B. The visited set should be an array instead

C. The graph object keys should be strings, not numbers

D. The function should return an array, not a set

Solution

1. Step 1: Check the neighbor visit condition

   It incorrectly calls dfs if neighbor is already visited, causing infinite recursion.

2. Step 2: Correct the condition

   Change to if (!visited.has(neighbor)) to visit unvisited neighbors only.

3. Final Answer:

   The condition should be if (!visited.has(neighbor)) instead of if (visited.has(neighbor)) -> Option A

4. Quick Check:

   Visit only unvisited neighbors [OK]

Hint: Call DFS only if neighbor not visited [OK]

Common Mistakes:

• Calling DFS on already visited nodes
• Using wrong data structure for visited
• Returning wrong type from DFS

5. You want to find if there is a path from node 1 to node 5 in this graph:

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

function dfs(node, target, visited = new Set()) {
  if (node === target) return true;
  visited.add(node);
  for (const neighbor of graph[node]) {
    if (!visited.has(neighbor)) {
      if (dfs(neighbor, target, visited)) return true;
    }
  }
  return false;
}

console.log(dfs(1, 5));

What will be the output and why?

hard

A. false, because the visited set is not updated correctly

B. true, because DFS finds a path 1 -> 3 -> 5

C. true, because DFS visits all nodes regardless of target

D. false, because node 5 is not directly connected to 1

Solution

1. Step 1: Check DFS path search logic

   DFS returns true immediately when target node is found.

2. Step 2: Trace path from 1 to 5

   Path exists: 1 -> 3 -> 5, so DFS returns true.

3. Final Answer:

   true, because DFS finds a path 1 -> 3 -> 5 -> Option B

4. Quick Check:

   DFS finds path = true [OK]

Hint: DFS returns true when target found [OK]

Common Mistakes:

• Assuming direct connection needed
• Ignoring early return on target found
• Not updating visited set properly