DFS Depth First Search on Graph in DSA Go - Build from Scratch

DFS Depth First Search on Graph

📖 Scenario: You are exploring a map of connected cities. Each city is linked to some other cities by roads. You want to visit all cities starting from a specific city, going as deep as possible before backtracking. This is like exploring a maze by always going forward until you cannot go further, then backtracking.

🎯 Goal: Build a program that uses Depth First Search (DFS) to visit all cities reachable from a starting city in a graph represented by adjacency lists.

📋 What You'll Learn

Create a graph using a map where keys are city names (strings) and values are slices of connected city names.

Create a map to keep track of visited cities.

Write a DFS function that visits cities recursively.

Print the order of cities visited starting from a given city.

💡 Why This Matters

🌍 Real World

DFS is used in many real-world problems like maze solving, network traversal, and scheduling tasks.

💼 Career

Understanding DFS is essential for software engineers working on algorithms, game development, and systems programming.

1

Create the graph data structure

Create a variable called graph of type map[string][]string with these exact entries: "A": {"B", "C"}, "B": {"D"}, "C": {"E"}, "D": {}, "E": {}.

DSA Go

# Your code here

Hint

Use a map with string keys and slice of strings as values to represent the graph.

2

Create the visited map

Add a variable called visited of type map[string]bool and initialize it as an empty map.

DSA Go

package main

func main() {
    graph := map[string][]string{
        "A": {"B", "C"},
        "B": {"D"},
        "C": {"E"},
        "D": {},
        "E": {},
    }
    // Create visited map
    // Your code here
}

Hint

Use make(map[string]bool) to create an empty map for visited cities.

3

Write the DFS function

Write a function called dfs that takes parameters city string, graph map[string][]string, and visited map[string]bool. Inside, mark city as visited, then for each connected city in graph[city], if it is not visited, call dfs recursively on it.

DSA Go

package main

func main() {
    graph := map[string][]string{
        "A": {"B", "C"},
        "B": {"D"},
        "C": {"E"},
        "D": {},
        "E": {},
    }
    visited := make(map[string]bool)

    // Write dfs function here
    // Your code here
}

Hint

Use recursion to visit each connected city if it is not visited yet.

4

Run DFS and print visited cities

In main, call dfs with starting city "A", passing graph and visited. This will print the cities in the order they are visited.

DSA Go

package main

import "fmt"

func dfs(city string, graph map[string][]string, visited map[string]bool) {
    visited[city] = true
    fmt.Println(city)
    for _, nextCity := range graph[city] {
        if !visited[nextCity] {
            dfs(nextCity, graph, visited)
        }
    }
}

func main() {
    graph := map[string][]string{
        "A": {"B", "C"},
        "B": {"D"},
        "C": {"E"},
        "D": {},
        "E": {},
    }
    visited := make(map[string]bool)

    // Call dfs starting from "A"
    // Your code here
}

Hint

Call dfs("A", graph, visited) to start visiting from city A.

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