DFS Depth First Search on Graph in DSA Go

Mental Model

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

Analogy: Imagine exploring a maze by always taking the first unexplored path you see until you hit a dead end, then backtracking to try other paths.

Graph adjacency list:
0 -> [1, 2]
1 -> [2]
2 -> [0, 3]
3 -> [3]
Start at node 2 ↑

Dry Run Walkthrough

Input: Graph edges: 0->1, 0->2, 1->2, 2->0, 2->3, 3->3; start DFS at node 2

Goal: Visit all nodes reachable from node 2 in depth-first order

Step 1: Start DFS at node 2, mark 2 visited

Visited: {2}
Stack: [2]

Why: We begin exploring from node 2

Step 2: From 2, go to neighbor 0, mark 0 visited

Visited: {2, 0}
Stack: [2, 0]

Why: Explore first neighbor of 2 deeply

Step 3: From 0, go to neighbor 1, mark 1 visited

Visited: {2, 0, 1}
Stack: [2, 0, 1]

Why: Go deeper from 0 to 1

Step 4: From 1, neighbor 2 already visited, backtrack to 0

Visited: {2, 0, 1}
Stack: [2, 0]

Why: No new nodes from 1, backtrack

Step 5: From 0, neighbor 2 already visited, backtrack to 2

Visited: {2, 0, 1}
Stack: [2]

Why: No new nodes from 0, backtrack

Step 6: From 2, go to neighbor 3, mark 3 visited

Visited: {2, 0, 1, 3}
Stack: [2, 3]

Why: Explore next neighbor of 2

Step 7: From 3, neighbor 3 already visited (self-loop), backtrack to 2

Visited: {2, 0, 1, 3}
Stack: [2]

Why: No new nodes from 3, backtrack

Step 8: All neighbors of 2 visited, DFS complete

Visited: {2, 0, 1, 3}
Stack: []

Why: Traversal finished

Result:

Visited nodes in order: 2 -> 0 -> 1 -> 3

Annotated Code

DSA Go

package main

import "fmt"

// Graph represents a directed graph using adjacency list
type Graph struct {
	adjacency map[int][]int
}

// NewGraph creates a new graph
func NewGraph() *Graph {
	return &Graph{adjacency: make(map[int][]int)}
}

// AddEdge adds a directed edge from src to dest
func (g *Graph) AddEdge(src, dest int) {
	g.adjacency[src] = append(g.adjacency[src], dest)
}

// DFS performs depth-first search starting from start node
func (g *Graph) DFS(start int) []int {
	visited := make(map[int]bool)
	result := []int{}
	var dfsHelper func(int)
	dfsHelper = func(node int) {
		if visited[node] {
			return // already visited
		}
		visited[node] = true // mark visited
		result = append(result, node) // record visit
		for _, neighbor := range g.adjacency[node] {
			dfsHelper(neighbor) // visit neighbors recursively
		}
	}
	dfsHelper(start)
	return result
}

func main() {
	g := NewGraph()
	g.AddEdge(0, 1)
	g.AddEdge(0, 2)
	g.AddEdge(1, 2)
	g.AddEdge(2, 0)
	g.AddEdge(2, 3)
	g.AddEdge(3, 3)

	order := g.DFS(2)
	for i, node := range order {
		if i > 0 {
			fmt.Print(" -> ")
		}
		fmt.Print(node)
	}
	fmt.Println()
}

if visited[node] { return }

skip nodes already visited to avoid cycles

visited[node] = true

mark current node as visited

result = append(result, node)

record node visit order

for _, neighbor := range g.adjacency[node] { dfsHelper(neighbor) }

recursively visit all neighbors deeply

Output

2 -> 0 -> 1 -> 3

Complexity Analysis

Time: O(V + E) because DFS visits every vertex and edge once

Space: O(V) for the visited map and recursion stack in worst case

vs Alternative: Compared to BFS, DFS uses recursion and explores deep paths first, which can be more memory efficient for sparse graphs

Edge Cases

Empty graph

DFS returns empty traversal since no nodes exist

DSA Go

if visited[node] { return }

Single node with no edges

DFS visits the single node and stops

DSA Go

visited[node] = true

Graph with cycles (like node 3 pointing to itself)

DFS avoids infinite loops by checking visited nodes

DSA Go

if visited[node] { return }

When to Use This Pattern

When a problem asks to explore all connected parts of a graph deeply or find paths, use DFS because it explores one path fully before backtracking.

Common Mistakes

Mistake: Not marking nodes as visited before recursive calls, causing infinite loops
Fix: Mark nodes as visited immediately when first visiting them

Mistake: Visiting neighbors in wrong order or skipping some neighbors
Fix: Iterate over all neighbors in adjacency list and call DFS recursively on each

Summary

DFS visits nodes by going deep into each branch before backtracking.

Use DFS to explore all nodes reachable from a start node or to find paths in graphs.

The key is to mark nodes visited to avoid cycles and to recurse on neighbors fully before moving on.

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