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

Recall & Review

beginner

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

DFS explores as far as possible along each branch before backtracking. It goes deep into one path before trying another.

beginner

In DFS, how do we keep track of which nodes have been visited?

We use a 'visited' set or array to mark nodes that have already been explored to avoid revisiting them.

intermediate

What data structure is commonly used to implement DFS iteratively?

A stack is used to keep track of nodes to visit next, following the last-in, first-out order.

intermediate

How does DFS differ from Breadth First Search (BFS)?

DFS goes deep into one path before backtracking, while BFS explores all neighbors at the current depth before going deeper.

beginner

What is a common use case for DFS in graphs?

DFS is used for tasks like detecting cycles, finding connected components, and pathfinding in mazes.

What does DFS use to remember which nodes to visit next in its recursive form?

A Call stack

B Queue

C Hash map

D Priority queue

In recursive DFS, the system call stack keeps track of nodes to visit next.

Which of the following is true about DFS?

A It explores neighbors level by level

B It uses a queue to store nodes

C It cannot detect cycles

D It explores as deep as possible before backtracking

DFS explores as deep as possible along each branch before backtracking.

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

A O(V^2)

B O(V + E)

C O(E^2)

D O(log V)

DFS visits every vertex and edge once, so time complexity is O(V + E).

Which data structure is NOT typically used in DFS implementations?

A Stack

B Call stack

C Queue

D Visited set

Queues are used in BFS, not DFS.

What happens if you do not mark nodes as visited in DFS?

A It may revisit nodes and get stuck in cycles

B The algorithm runs faster

C It will find the shortest path

D It will use less memory

Without marking visited nodes, DFS can revisit nodes and enter infinite loops in cyclic graphs.

Explain how DFS explores a graph starting from a given node.

Think about going deep into one path before trying others.

Describe how you would implement DFS iteratively using a stack.

Use a stack to remember where to go next instead of recursion.

Practice

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

easy

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

B. Visit all neighbors of a node before moving deeper

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

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 others.

2. Step 2: Compare options with DFS behavior

   Explore as far as possible along each branch before backtracking matches this behavior exactly, while others describe BFS or incorrect methods.

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 neighbors first
• Assuming DFS visits nodes by distance

2. Which of the following is the correct way to start a DFS function in Go for a graph represented as adjacency list graph map[int][]int?

easy

A. func dfs(node int, visited map[int]bool) {}

B. func dfs(node int, visited []int) {}

C. func dfs(node int, visited map[int]int) {}

D. func dfs(node int, visited []bool) {}

Solution

1. Step 1: Identify correct visited type for DFS

   Visited should be a map[int]bool to mark nodes visited or not.

2. Step 2: Check options for visited parameter type

   Only func dfs(node int, visited map[int]bool) {} uses map[int]bool, others use incorrect types.

3. Final Answer:

   func dfs(node int, visited map[int]bool) {} -> Option A

4. Quick Check:

   Visited map with bool = correct DFS parameter [OK]

Hint: Use map[int]bool to track visited nodes in Go DFS [OK]

Common Mistakes:

• Using slice instead of map for visited
• Using wrong map value type
• Ignoring visited parameter

3. What is the output of the following Go code snippet using DFS on the graph?

graph := map[int][]int{
  1: {2, 3},
  2: {4},
  3: {},
  4: {},
}
visited := map[int]bool{}
var result []int
var dfs func(int)
dfs = func(node int) {
  if visited[node] {
    return
  }
  visited[node] = true
  result = append(result, node)
  for _, n := range graph[node] {
    dfs(n)
  }
}
dfs(1)
fmt.Println(result)

medium

A. [1 2 4 3]

B. [1 3 2 4]

C. [1 2 3 4]

D. [1 4 2 3]

Solution

1. Step 1: Trace DFS starting at node 1

   Visit 1, then go to 2, then 4 (no children), backtrack, then visit 3.

2. Step 2: Record order of visited nodes

   Order is 1, 2, 4, 3 as DFS explores deep before backtracking.

3. Final Answer:

   [1 2 4 3] -> Option A

4. Quick Check:

   DFS order = [1 2 4 3] [OK]

Hint: Follow each branch fully before moving to next neighbor [OK]

Common Mistakes:

• Visiting neighbors in wrong order
• Confusing BFS order with DFS
• Not marking visited nodes

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

func dfs(node int, graph map[int][]int, visited map[int]bool) {
  if visited[node] {
    return
  }
  visited[node] = true
  for _, n := range graph[node] {
    dfs(n, graph, visited)
  }
}

// Called as dfs(1, graph, visited)

medium

A. Missing base case to stop recursion

B. Visited map is not updated correctly

C. Incorrect parameter types in function

D. No code to process or print the node

Solution

1. Step 1: Analyze DFS function behavior

   Function marks visited and recurses but does not process or print nodes.

2. Step 2: Identify missing action

   DFS usually processes nodes (e.g., print or collect), missing here causes no visible output.

3. Final Answer:

   No code to process or print the node -> Option D

4. Quick Check:

   DFS missing node processing step [OK]

Hint: DFS must process nodes inside function [OK]

Common Mistakes:

• Assuming marking visited is enough
• Forgetting to print or collect nodes
• Thinking recursion stops without base case

5. Given a graph with possible cycles, how can you modify DFS in Go to detect if a cycle exists?

hard

A. Only mark nodes visited after all neighbors are processed

B. Use a recursion stack map to track nodes currently in the call stack

C. Use BFS instead of DFS to detect cycles

D. Ignore visited nodes and traverse all edges

Solution

1. Step 1: Understand cycle detection in DFS

   Detect cycles by tracking nodes currently in recursion stack to find back edges.

2. Step 2: Choose correct method

   Using a recursion stack map helps detect if a node is revisited while still in the current path.

3. Final Answer:

   Use a recursion stack map to track nodes currently in the call stack -> Option B

4. Quick Check:

   Cycle detection = recursion stack tracking [OK]

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

Common Mistakes:

• Marking visited too late
• Using BFS which doesn't detect cycles easily
• Ignoring visited nodes causing infinite loops