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 see, going deep until you hit a dead end, then backtracking to try other paths.

Graph adjacency list:
0 -> 1 -> 2 -> null
1 -> 3 -> null
2 -> 4 -> null
3 -> null
4 -> null
↑ Start at node 0

Dry Run Walkthrough

Input: Graph with edges: 0-1, 0-2, 1-3, 2-4; start DFS at node 0

Goal: Visit all nodes reachable from node 0 in depth-first order

Step 1: Start DFS at node 0, mark 0 visited

Visited: [0]
Stack: [0]

Why: We begin exploring from node 0

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

Visited: [0, 1]
Stack: [0, 1]

Why: DFS goes deep by visiting first unvisited neighbor

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

Visited: [0, 1, 3]
Stack: [0, 1, 3]

Why: Continue deep exploration

Step 4: Node 3 has no unvisited neighbors, backtrack to 1

Visited: [0, 1, 3]
Stack: [0, 1]

Why: Dead end reached, backtrack

Step 5: Node 1 has no more unvisited neighbors, backtrack to 0

Visited: [0, 1, 3]
Stack: [0]

Why: All neighbors of 1 visited, backtrack

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

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

Why: Explore next neighbor of 0

Step 7: From 2, go to neighbor 4, mark 4 visited

Visited: [0, 1, 3, 2, 4]
Stack: [0, 2, 4]

Why: Go deep from 2

Step 8: Node 4 has no unvisited neighbors, backtrack to 2, then 0, then end

Visited: [0, 1, 3, 2, 4]
Stack: []

Why: All nodes visited, DFS complete

Result:

Visited order: 0 -> 1 -> 3 -> 2 -> 4

Annotated Code

DSA C

#include <stdio.h>
#include <stdbool.h>
#define MAX 5

// Graph represented as adjacency matrix
int graph[MAX][MAX] = {
    {0,1,1,0,0}, // neighbors of 0
    {0,0,0,1,0}, // neighbors of 1
    {0,0,0,0,1}, // neighbors of 2
    {0,0,0,0,0}, // neighbors of 3
    {0,0,0,0,0}  // neighbors of 4
};
bool visited[MAX] = {false};

void dfs(int node) {
    visited[node] = true; // mark current node visited
    printf("%d ", node); // print visited node
    for (int i = 0; i < MAX; i++) {
        if (graph[node][i] == 1 && !visited[i]) {
            dfs(i); // recursively visit neighbor
        }
    }
}

int main() {
    dfs(0); // start DFS at node 0
    printf("\n");
    return 0;
}

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

mark current node as visited to avoid revisiting

printf("%d ", node); // print visited node

output the node as we visit it

for (int i = 0; i < MAX; i++) {

check all possible neighbors of current node

if (graph[node][i] == 1 && !visited[i]) {

if neighbor exists and not visited, explore it

dfs(i); // recursively visit neighbor

go deep into neighbor node

Output

0 1 3 2 4 

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 which uses a queue and explores level by level, DFS uses recursion and explores depth first, both have similar time but different traversal order

Edge Cases

Graph with no edges (isolated nodes)

DFS visits only the start node since no neighbors exist

DSA C

if (graph[node][i] == 1 && !visited[i]) {

Graph with a single node

DFS visits the single node and ends

DSA C

visited[node] = true;

Graph with cycles

Visited array prevents infinite loops by skipping visited nodes

DSA C

if (graph[node][i] == 1 && !visited[i]) {

When to Use This Pattern

When you need to explore all nodes or paths deeply in a graph or tree, DFS is the pattern to use because it dives deep before backtracking.

Common Mistakes

Mistake: Not marking nodes as visited before recursive calls
Fix: Mark the node visited immediately when entering DFS to avoid infinite loops

Mistake: Visiting neighbors without checking if they are visited
Fix: Always check visited array before recursive DFS call

Summary

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

Use DFS when you want to explore all paths or connected components deeply.

The key insight is to mark nodes visited and recurse on neighbors to avoid cycles.

Practice

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

easy

A. Visit all nodes at the current depth before moving deeper

B. Visit nodes randomly without any order

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

D. Only visit nodes with no outgoing edges

Solution

1. Step 1: Understand DFS traversal

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

2. Step 2: Compare with other traversal methods

   BFS visits nodes level by level, but DFS goes deep first.

3. Final Answer:

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

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 nodes level-wise
• Assuming DFS visits nodes randomly

2. Which of the following is the correct way to start a DFS function in C for a graph represented by adjacency list adj and visited array visited?

easy

A. void dfs(int node) { visited[node] = 1; for(int i=0; i

B. void dfs(int node) { visited[node] = true; for(int i=0; i

C. void dfs(int node) { visited[node] = 0; for(int i=0; i

D. void dfs(int node) { visited[node] = 1; for(int i=0; i

Solution

1. Step 1: Mark current node as visited

   Set visited[node] = 1 (or true) to avoid revisiting.

2. Step 2: Traverse neighbors only if not visited

   Check if neighbor is unvisited before recursive DFS call to prevent infinite loops.

3. Final Answer:

   void dfs(int node) { visited[node] = 1; for(int i=0; i -> Option D

4. Quick Check:

   Mark visited and check before recursion [OK]

Hint: Always check visited before recursive DFS call [OK]

Common Mistakes:

• Not checking if neighbor is visited
• Using wrong visited value (0 instead of 1)
• Using .size() instead of .length in C arrays

3. Consider the following graph adjacency list:
0: [1, 2]
1: [2]
2: [0, 3]
3: [3]
Starting DFS from node 2, what is the order of nodes visited?

medium

A. [2, 3, 0, 1]

B. [2, 0, 1, 3]

C. [2, 0, 3, 1]

D. [2, 1, 0, 3]

Solution

1. Step 1: Start DFS at node 2

   Visit 2, mark visited. Neighbors: 0 and 3.

2. Step 2: Visit neighbor 0 first

   From 2, go to 0. Visit 0, neighbors: 1 and 2 (2 already visited).

3. Step 3: Visit neighbor 1 from 0

   Visit 1, neighbor: 2 (visited). Backtrack.

4. Step 4: Back to 2, visit neighbor 3

   Visit 3, neighbor: 3 (already visited). End.

5. Final Answer:

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

6. Quick Check:

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

Hint: Follow neighbors depth-first, mark visited to avoid repeats [OK]

Common Mistakes:

• Visiting nodes multiple times
• Visiting neighbors in wrong order
• Ignoring visited checks causing loops

4. The following DFS code has a bug. What is the error?

void dfs(int node) {
  visited[node] = 1;
  for(int i=0; i<adj[node].length; i++) {
    dfs(adj[node][i]);
  }
}

medium

A. Missing check if neighbor is already visited before recursive call

B. Visited array is not initialized

C. Incorrect loop condition syntax

D. Visited[node] should be set after recursion

Solution

1. Step 1: Analyze DFS recursion calls

   The code calls dfs on all neighbors without checking if they are visited.

2. Step 2: Identify risk of infinite recursion

   Without visited check, DFS may revisit nodes endlessly causing stack overflow.

3. Final Answer:

   Missing check if neighbor is already visited before recursive call -> Option A

4. Quick Check:

   Always check visited before recursion [OK]

Hint: Check visited before recursive DFS call to avoid loops [OK]

Common Mistakes:

• Assuming visited check is optional
• Setting visited after recursion
• Ignoring infinite recursion risk

5. Given a directed graph with possible cycles, how can DFS be modified to detect if a cycle exists?

hard

A. Use a recursion stack array to track nodes in the current path and check if a node is revisited in this stack

B. Only mark nodes visited after all neighbors are processed

C. Use BFS instead of DFS to detect cycles

D. Ignore visited array and rely on node values

Solution

1. Step 1: Understand cycle detection in DFS

   Detect cycles by tracking nodes currently in recursion (call) stack.

2. Step 2: Use recursion stack array

   Maintain an array marking nodes in current DFS path; if a neighbor is in this stack, a cycle exists.

3. Step 3: Differentiate from visited array

   Visited marks all visited nodes; recursion stack tracks current path only.

4. Final Answer:

   Use a recursion stack array to track nodes in the current path and check if a node is revisited in this stack -> Option A

5. Quick Check:

   Recursion stack detects cycles in DFS [OK]

Hint: Track recursion stack to find cycles during DFS [OK]

Common Mistakes:

• Confusing visited with recursion stack
• Using BFS for cycle detection in directed graphs
• Not tracking current path nodes