DFS Depth First Search on Graph in DSA Typescript

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 with edges: 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 2, go to neighbor 0, mark 0 visited

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

Why: DFS goes deep to first unvisited neighbor

Step 3: From 0, go to neighbor 1, mark 1 visited

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

Why: Continue deep exploration from 0 to 1

Step 4: From 1, neighbor 2 already visited, backtrack to 0

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

Why: No new nodes from 1, so backtrack

Step 5: From 0, neighbor 2 visited, backtrack to 2

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

Why: All neighbors of 0 visited, backtrack

Step 6: From 2, go to neighbor 3, mark 3 visited

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

Why: Explore next neighbor of 2

Step 7: From 3, neighbor 3 already visited (self-loop), backtrack to 2

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

Why: No new nodes from 3, backtrack

Step 8: All neighbors of 2 visited, DFS complete

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

Why: Traversal finished, all reachable nodes visited

Result:

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

Annotated Code

DSA Typescript

class Graph {
  adjacencyList: Map<number, number[]>;

  constructor() {
    this.adjacencyList = new Map();
  }

  addEdge(src: number, dest: number): void {
    if (!this.adjacencyList.has(src)) {
      this.adjacencyList.set(src, []);
    }
    this.adjacencyList.get(src)!.push(dest);
  }

  dfs(start: number): number[] {
    const visited = new Set<number>();
    const result: number[] = [];

    const dfsHelper = (node: number) => {
      visited.add(node); // mark node visited
      result.push(node); // record visit order

      const neighbors = this.adjacencyList.get(node) || [];
      for (const neighbor of neighbors) {
        if (!visited.has(neighbor)) {
          dfsHelper(neighbor); // recursively visit neighbors
        }
      }
    };

    dfsHelper(start);
    return result;
  }
}

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

const dfsOrder = graph.dfs(2);
console.log(dfsOrder.join(' -> '));

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

mark current node as visited to avoid revisiting

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

record the order of node visits

for (const neighbor of neighbors) { if (!visited.has(neighbor)) { dfsHelper(neighbor); } }

recursively visit each unvisited neighbor to explore deeply

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 (isolated nodes)

DFS visits only the start node since no neighbors exist

DSA Typescript

const neighbors = this.adjacencyList.get(node) || [];

Graph with self-loops

Self-loops do not cause infinite loops because visited nodes are tracked

DSA Typescript

if (!visited.has(neighbor)) { dfsHelper(neighbor); }

Start node not in graph

DFS visits only the start node as it has no neighbors

DSA Typescript

const neighbors = this.adjacencyList.get(node) || [];

When to Use This Pattern

When a problem requires exploring all connected parts of a graph deeply before backtracking, use DFS to traverse paths fully before trying alternatives.

Common Mistakes

Mistake: Not marking nodes as visited before recursive calls, causing infinite loops on cycles
Fix: Mark nodes as visited immediately when first visiting them to prevent revisiting

Summary

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

Use DFS when you want to explore all nodes reachable from a start point deeply.

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