DFS Depth First Search on Graph in DSA Typescript - Deep Dive

Overview - DFS Depth First Search on Graph

What is it?

Depth First Search (DFS) is a way to explore all the points (nodes) in a graph by going as deep as possible along each path before backtracking. Imagine starting at one node and moving to a connected node, then to another connected node, and so on, until you cannot go further. Then you step back and explore other paths. This method helps visit every node in a graph systematically.

Why it matters

Without DFS, finding paths, checking connections, or exploring networks would be slow and confusing. DFS helps solve problems like finding if two points are connected, detecting loops, or organizing tasks in order. It is a foundation for many algorithms used in maps, social networks, and computer programs. Without it, many technologies would be inefficient or impossible.

Where it fits

Before learning DFS, you should understand what graphs are and how they represent connections between points. After DFS, you can learn Breadth First Search (BFS), shortest path algorithms, and graph cycle detection. DFS is a key step in mastering graph algorithms and problem-solving.

Mental Model

Core Idea

DFS explores a graph by going deep along one path until it can't go further, then backtracks to explore other paths.

Think of it like...

Imagine exploring a maze by always taking the first unexplored path you find, going as far as you can, then retracing your steps to try other paths until the whole maze is explored.

Graph example:

  A
 / \
B   C
|   |
D - E

DFS starting at A:
A -> B -> D -> E -> C

Traversal path:
A
│
B
│
D
│
E
│
C

Build-Up - 7 Steps

1

Foundation

Understanding Graphs and Nodes

Concept: Learn what a graph is and how nodes connect with edges.

A graph is a collection of points called nodes connected by lines called edges. Nodes can represent anything like cities, people, or tasks. Edges show relationships or paths between nodes. Graphs can be directed (one-way connections) or undirected (two-way connections).

Result

You can visualize and represent connections between items clearly.

Understanding graphs is essential because DFS works by moving through these connections step-by-step.

2

Foundation

Representing Graphs in Code

Concept: Learn how to store graphs using adjacency lists.

An adjacency list stores each node and a list of nodes it connects to. For example, a graph with nodes A, B, C where A connects to B and C is stored as: { A: ['B', 'C'], B: [], C: [] } This is efficient for exploring neighbors.

Result

You can create a graph structure in code ready for traversal.

Choosing the right graph representation makes DFS easier and faster to implement.

3

Intermediate

Basic DFS Algorithm Steps

Concept: Learn the step-by-step process of DFS traversal.

Start at a chosen node, mark it as visited, then recursively visit each unvisited neighbor. If no neighbors are left, backtrack to the previous node and continue. This continues until all reachable nodes are visited.

Result

You can manually trace DFS on a small graph and understand the order nodes are visited.

Knowing the recursive nature of DFS helps understand how it explores deeply before backtracking.

4

Intermediate

Implementing DFS with Recursion

🤔Before reading on: do you think DFS can be implemented without loops, using only function calls? Commit to yes or no.

Concept: Use recursive function calls to explore nodes deeply.

In code, DFS is often written as a function that calls itself for each unvisited neighbor. This uses the call stack to remember where to backtrack. For example: function dfs(node, visited, graph) { visited.add(node); for (const neighbor of graph[node]) { if (!visited.has(neighbor)) { dfs(neighbor, visited, graph); } } } This visits all nodes reachable from the start.

Result

DFS visits nodes in depth-first order, exploring one path fully before others.

Understanding recursion is key because it naturally handles the backtracking in DFS.

5

Intermediate

Handling Cycles and Visited Nodes

🤔Before reading on: do you think DFS can get stuck in an infinite loop if the graph has cycles? Commit to yes or no.

Concept: Use a visited set to avoid revisiting nodes and infinite loops.

Graphs can have cycles, meaning you can return to the same node through different paths. Without tracking visited nodes, DFS would loop forever. By marking nodes as visited when first seen, DFS skips them later, preventing infinite loops.

Result

DFS safely explores graphs with cycles without repeating nodes endlessly.

Knowing to track visited nodes prevents common bugs and infinite loops in graph traversal.

6

Advanced

Iterative DFS Using a Stack

🤔Before reading on: do you think DFS requires recursion, or can it be done with a loop and a stack? Commit to your answer.

Concept: Implement DFS without recursion by using an explicit stack data structure.

Instead of recursion, DFS can use a stack to keep track of nodes to visit. The algorithm: 1. Push the start node onto the stack. 2. While the stack is not empty: a. Pop a node. b. If not visited, mark visited and push its neighbors. Example code: function dfsIterative(start, graph) { const visited = new Set(); const stack = [start]; while (stack.length > 0) { const node = stack.pop(); if (!visited.has(node)) { visited.add(node); for (const neighbor of graph[node]) { if (!visited.has(neighbor)) { stack.push(neighbor); } } } } return visited; } This simulates recursion with a stack.

Result

DFS can run without recursion, useful in languages or environments where recursion is limited.

Understanding the stack-based approach reveals the underlying mechanism of recursion and offers more control.

7

Expert

DFS Applications and Limitations

🤔Before reading on: do you think DFS always finds the shortest path between nodes? Commit to yes or no.

Concept: Explore what DFS can and cannot do, and where it fits in real problems.

DFS is great for exploring all nodes, detecting cycles, and ordering tasks (topological sort). However, it does not guarantee shortest paths; BFS is better for that. DFS can also be used in solving puzzles, maze generation, and checking connectivity. Understanding its limits helps choose the right tool.

Result

You know when to use DFS and when to prefer other algorithms.

Knowing DFS strengths and weaknesses prevents misuse and guides efficient problem solving.

Under the Hood

DFS uses a stack structure, either implicitly via recursion or explicitly, to remember the path it is exploring. Each time it visits a node, it pushes neighbors onto the stack and marks nodes as visited to avoid repeats. The call stack or explicit stack controls the order of exploration, ensuring deep traversal before backtracking.

Why designed this way?

DFS was designed to explore graphs deeply to solve problems like connectivity and cycle detection efficiently. Using recursion or a stack fits naturally with the problem's structure, allowing simple code and clear logic. Alternatives like BFS use queues for breadth exploration, but DFS's depth-first approach suits many tasks better.

DFS internal flow:

Start Node
   │
   ▼
[Push Start]
   │
   ▼
[Pop Node]
   │
   ▼
Mark Visited
   │
   ▼
Push Unvisited Neighbors
   │
   ▼
Repeat until stack empty

Stack (top): Neighbor nodes to visit
Visited Set: Nodes already explored

Myth Busters - 4 Common Misconceptions

Quick: Does DFS always find the shortest path between two nodes? Commit to yes or no.

Common Belief: DFS always finds the shortest path between nodes because it explores all paths.

Reality: DFS does not guarantee the shortest path; it explores deeply and may find longer paths first.

Why it matters: Using DFS for shortest path can lead to incorrect or inefficient solutions; BFS or Dijkstra's algorithm are better choices.

Quick: Can DFS get stuck in an infinite loop on graphs with cycles if you don't track visited nodes? Commit to yes or no.

Common Belief: DFS will never loop infinitely because it always moves forward.

Reality: Without marking visited nodes, DFS can revisit the same nodes endlessly in cyclic graphs.

Why it matters: Not tracking visited nodes causes infinite loops and crashes in programs.

Quick: Is recursion the only way to implement DFS? Commit to yes or no.

Common Belief: DFS must be implemented using recursion because it explores deeply.

Reality: DFS can be implemented iteratively using a stack, avoiding recursion.

Why it matters: Knowing iterative DFS helps in environments with limited recursion depth and improves control over traversal.

Quick: Does DFS always visit nodes in the same order regardless of graph representation? Commit to yes or no.

Common Belief: DFS visits nodes in a fixed order no matter how the graph is stored.

Reality: DFS visit order depends on the order of neighbors in the adjacency list or matrix.

Why it matters: Assuming fixed order can cause bugs when comparing DFS results or debugging.

Expert Zone

1

The order of neighbors in the adjacency list affects DFS traversal order and can change algorithm outcomes in some problems.

2

Using iterative DFS with an explicit stack can improve performance and avoid stack overflow in large graphs compared to recursion.

3

DFS can be modified to track entry and exit times of nodes, enabling advanced algorithms like finding articulation points and bridges.

When NOT to use

Avoid DFS when you need the shortest path between nodes; use Breadth First Search (BFS) or Dijkstra's algorithm instead. Also, for very large graphs with deep recursion, iterative DFS or other traversal methods are safer to prevent stack overflow.

Production Patterns

DFS is used in real-world systems for cycle detection in dependency graphs, solving puzzles and games, analyzing social networks for connectivity, and performing topological sorts in build systems and task scheduling.

Connections

Breadth First Search (BFS)

BFS explores graphs level by level, opposite to DFS's deep exploration.

Understanding DFS helps grasp BFS as a complementary approach, and knowing both is essential for graph problems.

Call Stack in Programming

DFS recursion uses the call stack to remember nodes to backtrack to.

Knowing how the call stack works clarifies why DFS recursion naturally backtracks and how iterative DFS mimics this with an explicit stack.

Maze Solving in Robotics

DFS is used to explore paths deeply in maze navigation algorithms.

Recognizing DFS in robotics shows how abstract graph algorithms apply to physical world problems like robot pathfinding.

Common Pitfalls

#1 Not marking nodes as visited causes infinite loops in cyclic graphs.

Wrong approach:

function dfs(node, graph) {
for (const neighbor of graph[node]) {
dfs(neighbor, graph);
}
}
// No visited set used

Correct approach:

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

Root cause:

Forgetting to track visited nodes misunderstands graph cycles and traversal safety.

#2 Using DFS to find shortest path leads to wrong answers.

Wrong approach:

function dfsShortestPath(start, end, graph) {
// DFS used to find shortest path
// Returns first found path
}

Correct approach:

Use BFS or Dijkstra's algorithm for shortest path instead of DFS.

Root cause:

Confusing traversal order with path length leads to misuse of DFS.

#3 Implementing DFS recursively without considering stack limits causes crashes on large graphs.

Wrong approach:

function dfs(node, visited, graph) {
visited.add(node);
for (const neighbor of graph[node]) {
if (!visited.has(neighbor)) {
dfs(neighbor, visited, graph);
}
}
}
// Called on very large graph

Correct approach:

Use iterative DFS with an explicit stack to avoid recursion depth limits.

Root cause:

Not accounting for environment recursion limits causes runtime errors.

Key Takeaways

DFS explores graphs by going deep along one path before backtracking, using recursion or a stack.

Tracking visited nodes is essential to avoid infinite loops in graphs with cycles.

DFS does not guarantee shortest paths; use BFS or other algorithms for that purpose.

DFS can be implemented both recursively and iteratively, each with its own advantages.

Understanding DFS's strengths and limits helps apply it effectively in real-world problems.