DFS Depth First Search on Graph in DSA C++ - 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 visiting neighbors one by one, going deeper until no new nodes are left to visit. It helps find paths, check connectivity, and explore structures in graphs.

Why it matters

Without DFS, exploring complex networks like social connections, maps, or web links would be inefficient or impossible to do systematically. DFS helps solve problems like finding if two points are connected, detecting cycles, or ordering tasks. Without it, many computer programs and algorithms would be slower or unable to solve important problems.

Where it fits

Before learning DFS, you should understand what graphs are and how they represent connections. After DFS, you can learn Breadth First Search (BFS), shortest path algorithms, and advanced graph algorithms like topological sort or strongly connected components.

Mental Model

Core Idea

DFS explores a graph by going deep along one path until it cannot 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 stepping back when you hit a dead end to try another path.

Graph nodes and edges:

  A
 / \
B   C
|   |
D - E

DFS starting at A:

Start at A
↓
Go to B
↓
Go to D
↓
Go to E
(backtrack since no new neighbors)
↓
Back to B (no new neighbors)
↓
Back to A
↓
Go to C
↓
Go to E (already visited, skip)

Visited order: A -> B -> D -> E -> C

Build-Up - 7 Steps

1

Foundation

Understanding Graphs and Nodes

Concept: Learn what a graph is and how nodes and edges represent connections.

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

Result

You can visualize and represent connections between items using graphs.

Understanding the structure of graphs is essential before exploring how to traverse or search them.

2

Foundation

Graph Representation in Code

Concept: Learn how to store graphs in a program using adjacency lists.

Graphs are often stored as adjacency lists: each node has a list of neighbors it connects to. For example, node A's list might be [B, C], meaning A connects to B and C. This is memory efficient and easy to use for traversal algorithms.

Result

You can represent any graph in code using adjacency lists.

Choosing the right graph representation affects how easily and efficiently you can explore it.

3

Intermediate

Basic DFS Algorithm Steps

Concept: Learn the step-by-step process of DFS using recursion.

DFS starts at a node, marks it visited, then recursively visits each unvisited neighbor. This continues until all reachable nodes are visited. The recursion stack keeps track of the path being explored.

Result

You can write a simple DFS function that visits all nodes reachable from a start node.

Recursion naturally fits DFS because it remembers the path and backtracks automatically.

4

Intermediate

Handling Visited Nodes to Avoid Loops

🤔Before reading on: do you think DFS can get stuck in infinite loops if we don't track visited nodes? Commit to yes or no.

Concept: Learn why marking nodes as visited is crucial to prevent revisiting and infinite loops.

Graphs can have cycles, meaning you can return to the same node by following edges. Without marking nodes visited, DFS would keep going in circles forever. We use a visited set or array to remember which nodes we have already explored.

Result

DFS safely explores graphs with cycles without repeating nodes endlessly.

Tracking visited nodes is the key to making DFS reliable and efficient on any graph.

5

Intermediate

Iterative DFS Using a Stack

🤔Before reading on: do you think DFS must always use recursion? Commit to yes or no.

Concept: Learn how to implement DFS without recursion using an explicit stack.

Instead of recursion, DFS can use a stack data structure to keep track of nodes to visit. Push the start node, then repeatedly pop a node, visit it, and push its unvisited neighbors. This simulates the call stack of recursion.

Result

You can perform DFS iteratively, which can be easier to control and avoids stack overflow.

Understanding iterative DFS reveals the underlying mechanics of recursion and offers more control in practice.

6

Advanced

DFS Applications: Cycle Detection and Connectivity

🤔Before reading on: do you think DFS can detect cycles in a graph? Commit to yes or no.

Concept: Learn how DFS helps find cycles and check if a graph is connected.

By tracking nodes currently in the recursion stack, DFS can detect cycles if it revisits a node still in the stack. Also, if DFS visits all nodes starting from one node, the graph is connected; otherwise, it has disconnected parts.

Result

You can use DFS to solve real problems like cycle detection and connectivity checks.

DFS is not just traversal; it is a powerful tool for analyzing graph properties.

7

Expert

DFS Internals: Call Stack and Memory Usage

🤔Before reading on: do you think DFS recursion depth equals the longest path in the graph? Commit to yes or no.

Concept: Understand how DFS uses the call stack and memory during execution.

Each recursive DFS call adds a frame to the call stack, representing the current node and its neighbors. The maximum recursion depth equals the longest path without cycles. Excessive depth can cause stack overflow. Iterative DFS avoids this by managing its own stack.

Result

You understand DFS's memory behavior and limitations in large or deep graphs.

Knowing DFS internals helps write safer, more efficient code and choose between recursive and iterative approaches.

Under the Hood

DFS works by using a stack structure, either implicitly via recursion or explicitly, to keep track of nodes to visit. When a node is visited, it is marked to avoid revisiting. The algorithm explores neighbors deeply before backtracking, ensuring all reachable nodes are covered. The call stack or explicit stack manages the path and backtracking automatically.

Why designed this way?

DFS was designed to explore graphs deeply and systematically with minimal memory overhead. Using recursion or a stack fits naturally with the problem of exploring paths. Alternatives like BFS explore breadth-wise but require queues and more memory. DFS's design balances simplicity and power for many graph problems.

DFS Internal Flow:

┌─────────────┐
│ Start Node  │
└──────┬──────┘
       │
       ▼
┌─────────────┐
│ Visit Node  │
│ Mark Visited│
└──────┬──────┘
       │
       ▼
┌─────────────┐
│ For each    │
│ neighbor:   │
│ if unvisited│
│ recurse or  │
│ push to stack│
└──────┬──────┘
       │
       ▼
┌─────────────┐
│ Backtrack   │
│ when no new │
│ neighbors   │
└─────────────┘

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 two nodes in a graph.

Reality: DFS does not guarantee the shortest path; it explores deeply and may find longer paths first. BFS is used to find shortest paths in unweighted graphs.

Why it matters: Using DFS to find shortest paths can lead to incorrect or inefficient solutions in pathfinding problems.

Quick: Can DFS be used on graphs with cycles without extra precautions? Commit to yes or no.

Common Belief: DFS works fine on any graph without tracking visited nodes.

Reality: Without marking visited nodes, DFS can enter infinite loops on graphs with cycles.

Why it matters: Failing to track visited nodes causes programs to hang or crash due to infinite recursion or loops.

Quick: Is iterative DFS always more efficient than recursive DFS? Commit to yes or no.

Common Belief: Iterative DFS is always faster and better than recursive DFS.

Reality: Iterative DFS avoids recursion limits but can be more complex to implement; recursive DFS is simpler and often efficient enough.

Why it matters: Choosing iterative DFS just for speed may add unnecessary complexity without real benefit in many cases.

Quick: Does DFS visit nodes in the same order every time? Commit to yes or no.

Common Belief: DFS always visits nodes in the same order regardless of graph representation or neighbor order.

Reality: DFS visit order depends on the order neighbors are stored and visited; different orders can lead to different traversal sequences.

Why it matters: Assuming fixed order can cause bugs when algorithms rely on specific traversal sequences.

Expert Zone

1

DFS traversal order can be controlled by sorting neighbors, which is critical in algorithms like topological sort or lexicographically smallest path finding.

2

In directed graphs, DFS can be used to find strongly connected components by combining it with low-link values and stack management (Tarjan's algorithm).

3

Recursive DFS can cause stack overflow on very deep or large graphs; iterative DFS or tail recursion optimization can mitigate this.

When NOT to use

DFS is not suitable when shortest paths are needed in unweighted graphs; use BFS instead. For weighted graphs, algorithms like Dijkstra's or A* are better. Also, DFS is less efficient for very wide graphs where BFS or heuristic searches perform better.

Production Patterns

DFS is used in production for tasks like cycle detection in dependency graphs, maze solving, parsing expressions, and exploring game states. It is often combined with memoization or pruning to optimize search in large state spaces.

Connections

Breadth First Search (BFS)

Opposite traversal strategy: BFS explores neighbors level by level, DFS explores deeply first.

Understanding DFS helps grasp BFS as a complementary approach, each suited for different problems like shortest path (BFS) vs. path existence (DFS).

Recursion in Programming

DFS naturally uses recursion to manage exploration paths and backtracking.

Mastering DFS deepens understanding of recursion mechanics, call stacks, and how problems can be broken down into smaller subproblems.

Human Problem Solving Strategies

DFS mirrors how humans explore options deeply before backtracking and trying alternatives.

Recognizing this connection helps appreciate DFS as a natural, intuitive method for exploring complex decision trees or puzzles.

Common Pitfalls

#1 Infinite recursion due to not marking visited nodes.

Wrong approach:

void dfs(int node) {
for (int neighbor : graph[node]) {
dfs(neighbor);
}
}
// No visited check

Correct approach:

void dfs(int node) {
visited[node] = true;
for (int neighbor : graph[node]) {
if (!visited[neighbor]) dfs(neighbor);
}
}

Root cause:

Not tracking visited nodes causes revisiting the same nodes endlessly in graphs with cycles.

#2 Assuming DFS finds shortest paths.

Wrong approach:

Use DFS to find shortest path by returning first found path without checking path length.

Correct approach:

Use BFS for shortest path in unweighted graphs, as it explores neighbors level-wise.

Root cause:

Misunderstanding DFS traversal order and its lack of shortest path guarantee.

#3 Stack overflow on large graphs using recursive DFS.

Wrong approach:

Recursive DFS on very deep graph without limits or iterative alternative.

Correct approach:

Implement iterative DFS using explicit stack to avoid call stack overflow.

Root cause:

Ignoring recursion depth limits of programming language environments.

Key Takeaways

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

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

DFS does not guarantee shortest paths; BFS is better for that purpose.

Understanding DFS internals helps choose between recursive and iterative implementations safely.

DFS is a foundational tool for many graph problems like cycle detection, connectivity, and path exploration.

Practice

1. What is the main idea behind Depth First Search (DFS) on a graph?

easy

A. Explore as far as possible along each branch before backtracking

B. Visit all neighbors of a node before moving deeper

C. Visit nodes in order of their distance from the start node

D. Randomly visit nodes without any order

Solution

1. Step 1: Understand DFS traversal

   DFS explores a graph by going deep into one branch before backtracking to explore other branches.

2. Step 2: Compare with other traversal methods

   BFS visits neighbors first, but DFS goes deep first, matching Explore as far as possible along each branch before backtracking.

3. Final Answer:

   Explore as far as possible along each branch before backtracking -> Option A

4. Quick Check:

   DFS = deep exploration first [OK]

Hint: DFS means go deep first, then backtrack [OK]

Common Mistakes:

• Confusing DFS with BFS
• Thinking DFS visits neighbors first
• Assuming DFS visits nodes by distance

2. Which of the following is the correct C++ syntax to start a DFS from node 0 using recursion?

easy

A. DFS(visited, graph, 0);

B. dfs(0, visited, graph);

C. dfs(graph, 0, visited);

D. dfs(visited, 0, graph);

Solution

1. Step 1: Check typical DFS function signature

   Usually, DFS is called as dfs(node, visited, graph) where node is current node.

2. Step 2: Match the correct order

   dfs(0, visited, graph); matches the common order: dfs(0, visited, graph).

3. Final Answer:

   dfs(0, visited, graph); -> Option B

4. Quick Check:

   Call dfs with node first [OK]

Hint: DFS call starts with node, then visited, then graph [OK]

Common Mistakes:

• Swapping argument order
• Using uppercase DFS instead of dfs
• Passing graph before node

3. What will be the output order of nodes visited by DFS starting from node 0 in the graph below?

Graph adjacency list:
0: [1, 2]
1: [3]
2: []
3: []

Assuming DFS visits neighbors in ascending order.

medium

A. [0, 3, 1, 2]

B. [0, 2, 1, 3]

C. [0, 1, 3, 2]

D. [0, 1, 2, 3]

Solution

1. Step 1: Start DFS at node 0

   Visit 0, then explore neighbors in ascending order: 1, then 2.

2. Step 2: Explore neighbor 1

   From 1, visit 3 (only neighbor), then backtrack.

3. Step 3: Explore neighbor 2

   Node 2 has no neighbors, so visit and backtrack.

4. Final Answer:

   [0, 1, 3, 2] -> Option C

5. Quick Check:

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

Hint: Visit neighbors in order, go deep first [OK]

Common Mistakes:

• Visiting node 2 before node 1
• Not backtracking properly
• Confusing BFS order with DFS

4. Given the following DFS code snippet, what is the error?

void dfs(int node, vector<bool> &visited, vector &graph) {
  visited[node] = true;
  for (int i = 0; i < graph[node].size(); i++) {
    int neighbor = graph[node][i];
    if (visited[neighbor] = false) {
      dfs(neighbor, visited, graph);
    }
  }
}

medium

A. The function should return an int instead of void

B. The loop should use 'i <= graph[node].size()' instead of '<'

C. The visited vector should be passed by value, not reference

D. The condition 'if (visited[neighbor] = false)' uses assignment instead of comparison

Solution

1. Step 1: Check the if condition inside the loop

   The condition uses '=' which assigns false instead of comparing.

2. Step 2: Understand the impact of assignment in condition

   This causes the condition to always be false, so DFS won't recurse properly.

3. Final Answer:

   The condition 'if (visited[neighbor] = false)' uses assignment instead of comparison -> Option D

4. Quick Check:

   Use '==' for comparison, not '=' [OK]

Hint: Use '==' to compare, not '=' [OK]

Common Mistakes:

• Using '=' instead of '==' in conditions
• Loop boundary off-by-one errors
• Passing visited by value causing no effect

5. You have a graph with 5 nodes (0 to 4) and edges: 0-1, 0-2, 1-3, 1-4. Using DFS starting at node 0, how can you modify the algorithm to count the number of nodes reachable from node 0?

hard

A. Add a counter variable incremented each time a node is visited during DFS

B. Count nodes after DFS by checking which nodes have no neighbors

C. Use BFS instead of DFS to count nodes reachable

D. Count nodes by summing the degrees of all nodes

Solution

1. Step 1: Understand counting reachable nodes

   Counting nodes visited during DFS means incrementing a counter when marking a node visited.

2. Step 2: Why other options fail

   Counting nodes with no neighbors or summing degrees won't give reachable count; BFS is alternative but not required.

3. Final Answer:

   Add a counter variable incremented each time a node is visited during DFS -> Option A

4. Quick Check:

   Count nodes when visited in DFS [OK]

Hint: Increment count inside DFS when visiting nodes [OK]

Common Mistakes:

• Counting nodes with no neighbors instead of visited
• Using BFS unnecessarily
• Summing degrees instead of counting visited