DFS Depth First Search on Graph in DSA C++

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 find, 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 DFS at node 2 ↑

Dry Run Walkthrough

Input: Graph 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 at node 2 to explore its neighbors

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

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

Why: Go deep to neighbor 0 before exploring others

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

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

Why: Continue deep traversal to neighbor 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, backtrack

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

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

Why: No new nodes from 0, backtrack

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

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

Why: Explore remaining neighbor 3

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 C++

#include <iostream>
#include <vector>
using namespace std;

class Graph {
public:
    int V;
    vector<vector<int>> adj;

    Graph(int V) {
        this->V = V;
        adj.resize(V);
    }

    void addEdge(int u, int v) {
        adj[u].push_back(v);
    }

    void DFSUtil(int v, vector<bool>& visited) {
        visited[v] = true; // mark current node visited
        cout << v << " "; // print visited node

        for (int neighbor : adj[v]) {
            if (!visited[neighbor]) {
                DFSUtil(neighbor, visited); // recurse to neighbor
            }
        }
    }

    void DFS(int start) {
        vector<bool> visited(V, false); // track visited nodes
        DFSUtil(start, visited);
        cout << endl;
    }
};

int main() {
    Graph g(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);

    cout << "DFS starting from node 2: ";
    g.DFS(2);

    return 0;
}

visited[v] = true; // mark current node visited

mark current node as visited to avoid revisiting

cout << v << " "; // print visited node

output the node as part of DFS traversal order

for (int neighbor : adj[v]) { if (!visited[neighbor]) { DFSUtil(neighbor, visited); } }

recursively visit all unvisited neighbors to go deep

vector<bool> visited(V, false); // track visited nodes

initialize visited array before DFS starts

Output

DFS starting from node 2: 2 0 1 3 

Complexity Analysis

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

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

vs Alternative: Compared to BFS, DFS uses recursion and explores depth first, but both have same time complexity

Edge Cases

Empty graph (no vertices)

No nodes to visit, DFS does nothing

DSA C++

vector<bool> visited(V, false); // track visited nodes

Graph with isolated nodes

DFS visits only nodes reachable from start node

DSA C++

if (!visited[neighbor]) { DFSUtil(neighbor, visited); }

Graph with self-loops

Self-loop does not cause infinite recursion due to visited check

DSA C++

if (!visited[neighbor]) { DFSUtil(neighbor, visited); }

When to Use This Pattern

When you need to explore all nodes reachable from a start point deeply before backtracking, use DFS to traverse graph paths fully.

Common Mistakes

Mistake: Not marking nodes as visited before recursion causing infinite loops
Fix: Mark node visited immediately when entering DFSUtil to prevent revisiting

Mistake: Visiting neighbors without checking if visited
Fix: Add visited check before recursive DFS call to avoid cycles

Summary

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

Use DFS when you want to explore all reachable nodes deeply or need path exploration.

The key is to mark nodes visited before recursion to avoid infinite loops.

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