DFS Depth First Search on Graph in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of DFS traversal on a simple graph

What is the output of the following DFS traversal starting from node 1?

DSA Go

package main

import "fmt"

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

func main() {
    graph := map[int][]int{
        1: {2, 3},
        2: {4},
        3: {},
        4: {},
    }
    visited := make(map[int]bool)
    var result []int
    dfs(graph, 1, visited, &result)
    fmt.Println(result)
}

A [1 3 2 4]

B [1 2 4 3]

C [1 2 3 4]

D [1 4 2 3]

💡 Hint

Remember DFS explores as far as possible along each branch before backtracking.

The DFS starts at node 1, visits 2 first, then 4 (neighbor of 2), backtracks to 1, then visits 3.

🧠 Conceptual

intermediate

Number of nodes visited in DFS

Given the graph below and starting DFS from node 0, how many nodes will be visited?

DSA Go

graph := map[int][]int{
    0: {1, 2},
    1: {2},
    2: {0, 3},
    3: {3},
    4: {5},
    5: {},
}

A 4

B 6

C 5

D 3

💡 Hint

Nodes 4 and 5 are disconnected from node 0.

Starting from node 0, DFS visits nodes 0,1,2,3. Nodes 4 and 5 are disconnected and not visited.

🔧 Debug

advanced

Identify the error in DFS implementation

What error will this DFS code produce when run?

DSA Go

func dfs(graph map[int][]int, start int, visited map[int]bool, result *[]int) {
    visited[start] = true
    *result = append(*result, start)
    for _, neighbor := range graph[start] {
        if visited[neighbor] {
            dfs(graph, neighbor, visited, result)
        }
    }
}

A Compilation error: missing return statement

B No error, runs correctly

C Stack overflow due to infinite recursion

D Runtime error: nil pointer dereference

💡 Hint

Check the condition that controls recursion to avoid revisiting nodes.

The condition incorrectly recurses when the neighbor is already visited, causing infinite recursion and stack overflow.

❓ Predict Output

advanced

DFS traversal order on graph with cycles

What is the output of DFS starting from node 'A' on this graph?

DSA Go

graph := map[string][]string{
    "A": {"B", "C"},
    "B": {"D", "E"},
    "C": {"F"},
    "D": {"B"},
    "E": {},
    "F": {"C"},
}

visited := make(map[string]bool)
var result []string
var dfs func(string)
dfs = func(node string) {
    visited[node] = true
    result = append(result, node)
    for _, neighbor := range graph[node] {
        if !visited[neighbor] {
            dfs(neighbor)
        }
    }
}
dfs("A")
fmt.Println(result)

A ["A" "B" "D" "E" "C" "F"]

B ["A" "C" "F" "B" "D" "E"]

C ["A" "B" "E" "D" "C" "F"]

D ["A" "C" "B" "F" "D" "E"]

💡 Hint

DFS explores neighbors in order, avoiding revisiting nodes due to cycles.

DFS visits A, then B, then D (neighbor of B), then E, backtracks to A, then visits C, then F.

🚀 Application

expert

Detect if a graph is connected using DFS

Given a graph represented as adjacency list, which code snippet correctly determines if the graph is connected?

A

func isConnected(graph map[int][]int) bool {
    visited := make(map[int]bool)
    for node := range graph {
        if !visited[node] {
            dfs(node, graph, visited)
        }
    }
    return len(visited) == len(graph)
}

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

B

func isConnected(graph map[int][]int) bool {
    visited := make(map[int]bool)
    dfs(0, graph, visited)
    return len(visited) == len(graph)
}

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

C

func isConnected(graph map[int][]int) bool {
    visited := make(map[int]bool)
    for node := range graph {
        dfs(node, graph, visited)
    }
    return len(visited) == len(graph)
}

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

D

func isConnected(graph map[int][]int) bool {
    visited := make(map[int]bool)
    var dfs func(int)
    dfs = func(node int) {
        visited[node] = true
        for _, neighbor := range graph[node] {
            if !visited[neighbor] {
                dfs(neighbor)
            }
        }
    }
    var start int
    for k := range graph {
        start = k
        break
    }
    dfs(start)
    return len(visited) == len(graph)
}

💡 Hint

Start DFS from one node and check if all nodes are visited.

Option D starts DFS from one arbitrary node and checks if all nodes are visited, correctly determining connectivity.

Option D runs DFS multiple times unnecessarily.

Option D assumes node 0 exists, which may not be true.

Option D runs DFS from every node, marking all visited but not checking connectivity properly.

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