DFS Depth First Search on Graph in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is Depth First Search (DFS) in graph traversal?

DFS is a method to explore a graph by starting at a node and exploring as far as possible along each branch before backtracking.

beginner

In DFS, what data structure is commonly used to keep track of nodes to visit next?

A stack is used to keep track of nodes to visit next, either explicitly or via recursion call stack.

beginner

Why do we mark nodes as visited in DFS?

Marking nodes as visited prevents revisiting the same node, avoiding infinite loops and repeated work.

intermediate

What is the order of node visits in DFS on a graph with nodes 1 connected to 2 and 3, and 2 connected to 4?

Starting at 1, DFS visits 1 → 2 → 4 → 3 (assuming neighbors are visited in numerical order).

intermediate

What is the time complexity of DFS on a graph with V vertices and E edges?

The time complexity is O(V + E) because each vertex and edge is visited once.

Which data structure is naturally used by recursive DFS?

A Heap

B Queue

C Stack

D Hash Table

Recursive DFS uses the call stack to keep track of nodes, which behaves like a stack.

What happens if you do not mark nodes as visited in DFS on a graph with cycles?

A DFS will terminate normally

B DFS will skip some nodes

C DFS will visit nodes in breadth order

D DFS may enter an infinite loop

Without marking visited nodes, DFS can revisit nodes endlessly in cycles, causing infinite loops.

In DFS, when do you backtrack?

A When all nodes are visited

B When no unvisited neighbors remain

C Before visiting any neighbor

D After visiting the first neighbor

Backtracking happens when the current node has no unvisited neighbors left to explore.

What is the first node visited in DFS starting from node 1 in a graph?

A Node 1

B Node 2

C Node 0

D Node with highest degree

DFS starts at the given start node, here node 1.

Which of these is NOT a use case of DFS?

A Finding shortest path in unweighted graph

B Finding connected components

C Topological sorting

D Detecting cycles

Shortest path in unweighted graphs is better found by BFS, not DFS.

Explain how DFS explores a graph starting from a node. Include how it uses the stack and visited nodes.

Think about going deep first before going wide.

Describe the time complexity of DFS and why it is O(V + E) for a graph with V vertices and E edges.

Consider how many times nodes and edges are processed.

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