DFS Depth First Search on Graph in DSA Go - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to start DFS from the given node.

DSA Go

func DFS(graph map[int][]int, start int, visited map[int]bool) {
    visited[start] = true
    for _, neighbor := range graph[start] {
        if !visited[[1]] {
            DFS(graph, neighbor, visited)
        }
    }
}

Drag options to blanks, or click blank then click option'

Aneighbor

Bvisited

Cstart

Dgraph

Attempts:

3 left

💡 Hint

Common Mistakes

Checking 'start' instead of 'neighbor' causes infinite recursion.

Checking 'visited' or 'graph' as keys causes errors.

We check if the neighbor node has been visited before calling DFS recursively on it.

2fill in blank

medium

Complete the code to print nodes in DFS order.

DSA Go

func DFSPrint(graph map[int][]int, start int, visited map[int]bool) {
    visited[start] = true
    fmt.Println([1])
    for _, neighbor := range graph[start] {
        if !visited[neighbor] {
            DFSPrint(graph, neighbor, visited)
        }
    }
}

Drag options to blanks, or click blank then click option'

Agraph

Bvisited

Cneighbor

Dstart

Attempts:

3 left

💡 Hint

Common Mistakes

Printing 'neighbor' prints nodes multiple times.

Printing 'graph' or 'visited' causes errors.

We print the current node 'start' before visiting neighbors to follow DFS order.

3fill in blank

hard

Fix the error in the DFS function to avoid revisiting nodes.

DSA Go

func DFS(graph map[int][]int, start int, visited map[int]bool) {
    if visited[[1]] {
        return
    }
    visited[start] = true
    for _, neighbor := range graph[start] {
        DFS(graph, neighbor, visited)
    }
}

Drag options to blanks, or click blank then click option'

Aneighbor

Bstart

Cvisited

Dgraph

Attempts:

3 left

💡 Hint

Common Mistakes

Checking 'neighbor' causes infinite recursion.

Checking 'visited' or 'graph' causes errors.

We check if the current node 'start' is already visited to stop recursion.

4fill in blank

hard

Fill both blanks to create a DFS function that returns the order of visited nodes.

DSA Go

func DFSOrder(graph map[int][]int, start int, visited map[int]bool, order *[]int) {
    visited[[1]] = true
    *order = append(*order, [2])
    for _, neighbor := range graph[start] {
        if !visited[neighbor] {
            DFSOrder(graph, neighbor, visited, order)
        }
    }
}

Drag options to blanks, or click blank then click option'

Astart

Bneighbor

Cvisited

Dgraph

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'neighbor' instead of 'start' causes wrong order.

Using 'visited' or 'graph' causes errors.

Mark the current node 'start' as visited and append it to the order slice.

5fill in blank

hard

Fill all three blanks to implement DFS that counts connected components in a graph.

DSA Go

func CountComponents(graph map[int][]int) int {
    visited := make(map[int]bool)
    count := 0
    for node := range graph {
        if !visited[[1]] {
            DFSCount(graph, [2], visited)
            count[3]
        }
    }
    return count
}

func DFSCount(graph map[int][]int, start int, visited map[int]bool) {
    visited[start] = true
    for _, neighbor := range graph[start] {
        if !visited[neighbor] {
            DFSCount(graph, neighbor, visited)
        }
    }
}

Drag options to blanks, or click blank then click option'

Anode

Bstart

C++

D+=

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'start' instead of 'node' in the loop causes errors.

Using '+=' instead of '++' changes count incorrectly.

Check if 'node' is visited, call DFSCount on 'node', then increment count by 1.

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