DFS Depth First Search on Graph in DSA C++ - Build from Scratch

DFS Depth First Search on Graph

📖 Scenario: You are working with a small network of connected computers. Each computer is represented as a node in a graph. You want to explore all computers reachable from a starting computer using Depth First Search (DFS).

🎯 Goal: Build a program that performs DFS on a graph represented by an adjacency list. You will create the graph, set up a visited list, implement DFS, and print the order in which nodes are visited.

📋 What You'll Learn

Create an adjacency list for a graph with 5 nodes (0 to 4) and specific edges

Create a visited boolean vector to track visited nodes

Implement DFS function using recursion

Print the nodes in the order they are visited starting from node 0

💡 Why This Matters

🌍 Real World

DFS is used in many real-world applications like network traversal, puzzle solving, and pathfinding in maps.

💼 Career

Understanding DFS is essential for software engineers working with graphs, algorithms, and complex data structures.

1

Create the graph adjacency list

Create a vector of vectors called graph with 5 nodes (0 to 4). Add edges as follows: 0 connected to 1 and 2, 1 connected to 3, 2 connected to 4.

DSA C++

# Your code here to create the graph adjacency list

Hint

Use vector> graph(5); to create 5 nodes. Assign neighbors using graph[index] = {neighbors};.

2

Create the visited vector

Create a vector of booleans called visited with size 5, initialized to false for all nodes.

DSA C++

#include 
#include 

using namespace std;

int main() {
    vector> graph(5);
    graph[0] = {1, 2};
    graph[1] = {3};
    graph[2] = {4};
    graph[3] = {};
    graph[4] = {};

    vector visited(5, false);  // Your code here to create visited vector

    return 0;
}

Hint

Use vector visited(5, false); to create a visited list for 5 nodes.

3

Implement the DFS function

Write a recursive function called dfs that takes int node, vector>& graph, and vector& visited. Mark the current node as visited, then call dfs on all unvisited neighbors.

DSA C++

#include 
#include 

using namespace std;

void dfs(int node, vector>& graph, vector& visited) {
    // Mark node visited
    // Visit all neighbors recursively
}

int main() {
    vector> graph(5);
    graph[0] = {1, 2};
    graph[1] = {3};
    graph[2] = {4};
    graph[3] = {};
    graph[4] = {};

    vector visited(5, false);

    return 0;
}

Hint

Mark the current node visited with visited[node] = true;. Loop over neighbors with for (int neighbor : graph[node]). Call dfs recursively on unvisited neighbors.

4

Run DFS and print visited nodes

In main, call dfs(0, graph, visited); to start DFS from node 0. Then print all nodes in the order they were visited by checking visited vector and printing node numbers with a space between them.

DSA C++

#include 
#include 

using namespace std;

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

int main() {
    vector> graph(5);
    graph[0] = {1, 2};
    graph[1] = {3};
    graph[2] = {4};
    graph[3] = {};
    graph[4] = {};

    vector visited(5, false);

    dfs(0, graph, visited);

    // Print visited nodes in order
    // Your code here

    return 0;
}

Hint

Call dfs(0, graph, visited);. Then loop from 0 to 4 and print nodes where visited[i] is true, separated by spaces.

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