DFS Depth First Search on Graph in DSA Go - Deep Dive

Overview - DFS Depth First Search on Graph

What is it?

Depth First Search (DFS) is a way to explore all the points (nodes) in a graph by going as deep as possible along each path before backtracking. Imagine starting at one node and visiting neighbors one by one, diving deeper until no new nodes are left to visit. It helps find paths, check connections, and explore structures in graphs.

Why it matters

Without DFS, we would struggle to explore complex networks like social connections, maps, or computer networks efficiently. It solves the problem of visiting every part of a graph without missing or repeating nodes unnecessarily. This makes tasks like finding routes, detecting cycles, or checking connectivity possible in many real-world systems.

Where it fits

Before learning DFS, you should understand what graphs are and how they represent connections between points. After DFS, you can learn other graph algorithms like Breadth First Search (BFS), shortest path algorithms, or graph traversal optimizations.

Mental Model

Core Idea

DFS explores a graph by going as far as possible down one path before stepping back and trying another path.

Think of it like...

DFS is like exploring a maze by always taking the first unexplored path you see, going deep until you hit a dead end, then backtracking to try other paths.

Start
  |
  v
Node A
  |
  v
Node B
  |
  v
Node C (dead end)
  ^
  |
Backtrack to B
  |
  v
Node D
  |
  v
... (continues)

Build-Up - 7 Steps

1

Foundation

Understanding Graphs and Nodes

Concept: Graphs are made of nodes connected by edges; understanding this is key to DFS.

A graph is a collection of points called nodes. Each node can connect to other nodes via edges. These connections can be one-way or two-way. For example, a map of cities connected by roads is a graph where cities are nodes and roads are edges.

Result

You can picture a graph as dots connected by lines, ready to be explored.

Knowing what a graph is helps you understand what DFS will explore and why visiting nodes matters.

2

Foundation

What Does Traversal Mean?

Concept: Traversal means visiting nodes in a graph in a systematic way.

Traversal is like walking through a graph, visiting nodes one by one. The goal is to visit every node without missing any. DFS is one way to do this, by going deep into one path before trying others.

Result

You understand that traversal is the process of visiting nodes, which DFS performs deeply.

Understanding traversal sets the stage for why DFS chooses certain paths and order.

3

Intermediate

How DFS Explores Nodes

🤔Before reading on: Do you think DFS visits nodes in a wide or deep manner? Commit to your answer.

Concept: DFS visits nodes by going deep along one path before backtracking to explore others.

Starting from a node, DFS visits a neighbor, then a neighbor of that neighbor, and so on until it reaches a node with no unvisited neighbors. Then it backtracks to the previous node to check for other neighbors. This continues until all reachable nodes are visited.

Result

Nodes are visited in a path-first order, diving deep before moving sideways.

Knowing DFS's deep-first approach explains why it can find paths and detect cycles effectively.

4

Intermediate

Tracking Visited Nodes

🤔Before reading on: Do you think DFS needs to remember visited nodes? Why or why not? Commit your answer.

Concept: DFS keeps track of visited nodes to avoid visiting the same node multiple times and getting stuck.

When DFS visits a node, it marks it as visited. Before visiting a neighbor, it checks if that neighbor was visited. This prevents infinite loops in graphs with cycles and ensures each node is processed once.

Result

DFS visits each node exactly once, even in graphs with loops.

Understanding visited tracking prevents confusion about infinite loops and repeated visits.

5

Intermediate

Implementing DFS with Recursion

🤔Before reading on: Do you think DFS can be done without loops? Commit your answer.

Concept: DFS can be implemented using recursion, where the function calls itself to explore neighbors deeply.

In recursion, DFS calls itself for each unvisited neighbor. When no neighbors remain, the function returns, backtracking to previous calls. This natural call stack manages the order of exploration without explicit loops.

Result

DFS explores nodes deeply using the program's call stack automatically.

Knowing recursion simplifies DFS implementation and clarifies its deep exploration.

6

Advanced

Iterative DFS Using a Stack

🤔Before reading on: Can DFS be done without recursion? Commit your answer.

Concept: DFS can be done iteratively using a stack data structure to manage nodes to visit next.

Instead of recursion, DFS uses a stack to store nodes. Start by pushing the initial node. Then pop a node, visit it, and push its unvisited neighbors. Repeat until the stack is empty. This mimics recursion but uses explicit memory.

Result

DFS can run without recursion, useful in languages or situations where recursion is limited.

Understanding iterative DFS reveals how recursion is just a hidden stack, helping with memory control.

7

Expert

DFS Applications and Cycle Detection

🤔Before reading on: Does DFS help detect cycles in graphs? Commit your answer.

Concept: DFS can detect cycles by tracking nodes currently in the recursion stack during traversal.

While visiting nodes, DFS marks nodes as 'in progress'. If it reaches a neighbor already 'in progress', a cycle exists. This is useful in detecting loops in dependency graphs or deadlocks.

Result

DFS not only explores but also identifies cycles, aiding in complex graph analysis.

Knowing DFS's role in cycle detection unlocks its power in real-world problems like scheduling and deadlock prevention.

Under the Hood

DFS uses a stack structure, either implicitly via recursion or explicitly, to remember which nodes to visit next. It marks nodes as visited to avoid revisiting. The call stack or explicit stack pushes nodes as it explores neighbors deeply, backtracking when no new nodes remain. This process ensures all reachable nodes are visited in a depth-first order.

Why designed this way?

DFS was designed to explore graphs efficiently by diving deep into paths, which helps find paths and cycles quickly. Using recursion or a stack simplifies the logic and leverages existing program structures. Alternatives like BFS explore breadth-first but are less suited for path or cycle detection in some cases.

Start
  ↓
[Node]
  ↓
Push neighbors onto stack
  ↓
Pop next node
  ↓
If unvisited, visit and push neighbors
  ↓
Repeat until stack empty
  ↓
End

Myth Busters - 4 Common Misconceptions

Quick: Does DFS always find the shortest path between nodes? Commit yes or no.

Common Belief: DFS always finds the shortest path between two nodes.

Reality: DFS does not guarantee the shortest path; it explores deeply and may find longer paths first.

Why it matters: Relying on DFS for shortest paths can lead to inefficient or incorrect solutions in routing or navigation.

Quick: Can DFS work without marking visited nodes? Commit yes or no.

Common Belief: DFS can work fine without tracking visited nodes.

Reality: Without marking visited nodes, DFS can get stuck in infinite loops in graphs with cycles.

Why it matters: Not tracking visited nodes causes programs to hang or crash due to endless recursion or looping.

Quick: Is recursion the only way to implement DFS? Commit yes or no.

Common Belief: DFS must be implemented using recursion.

Reality: DFS can be implemented iteratively using a stack, avoiding recursion.

Why it matters: Knowing iterative DFS helps in environments where recursion depth is limited or stack overflow is a risk.

Quick: Does DFS visit nodes in the order they appear in the graph? Commit yes or no.

Common Belief: DFS visits nodes in the order they appear in the graph data structure.

Reality: DFS visits nodes based on the order neighbors are explored, which depends on graph representation and neighbor order.

Why it matters: Assuming fixed order can cause confusion when debugging or comparing DFS outputs.

Expert Zone

1

DFS's performance depends heavily on graph representation; adjacency lists are more efficient than adjacency matrices for sparse graphs.

2

The order in which neighbors are visited affects DFS traversal order and can change results in algorithms like topological sorting.

3

In directed graphs, DFS can be used to find strongly connected components by combining it with other algorithms like Tarjan's.

When NOT to use

DFS is not ideal when you need the shortest path or minimum steps between nodes; Breadth First Search (BFS) is better for unweighted graphs. For weighted graphs, algorithms like Dijkstra's or A* are preferred.

Production Patterns

DFS is used in real systems for cycle detection in dependency graphs, solving puzzles like mazes, checking connectivity in networks, and performing topological sorts in build systems or task scheduling.

Connections

Breadth First Search (BFS)

BFS explores graphs level by level, opposite to DFS's deep exploration.

Understanding DFS helps grasp BFS as a complementary approach, useful for shortest paths and different traversal needs.

Call Stack in Programming

DFS recursion uses the call stack to manage exploration order.

Knowing how the call stack works clarifies how DFS manages backtracking and why recursion depth matters.

Maze Solving in Robotics

DFS strategy mimics how robots explore mazes by going deep before backtracking.

Seeing DFS in robotics shows how abstract algorithms solve real-world navigation and exploration problems.

Common Pitfalls

#1 Not marking nodes as visited causes infinite loops in graphs with cycles.

Wrong approach:

func DFS(node int) {
fmt.Println(node)
for _, neighbor := range graph[node] {
DFS(neighbor)
}
}

Correct approach:

var visited = make(map[int]bool)
func DFS(node int) {
if visited[node] {
return
}
visited[node] = true
fmt.Println(node)
for _, neighbor := range graph[node] {
DFS(neighbor)
}
}

Root cause:

Missing visited tracking means DFS revisits nodes endlessly in cycles.

#2 Using DFS to find shortest path in an unweighted graph leads to wrong results.

Wrong approach:

Use DFS to find shortest path by returning first found path without checking others.

Correct approach:

Use BFS to find shortest path as it explores neighbors level by level.

Root cause:

DFS explores deeply and may find longer paths first, not shortest.

#3 Assuming recursion depth is unlimited causes stack overflow on large graphs.

Wrong approach:

func DFS(node int) {
if visited[node] {
return
}
visited[node] = true
for _, neighbor := range graph[node] {
DFS(neighbor)
}
}
// Called on very large graph without limits

Correct approach:

Implement DFS iteratively using a stack to avoid recursion limits.

Root cause:

Recursion depth is limited by system stack size; large graphs cause overflow.

Key Takeaways

DFS explores graphs by going deep along paths before backtracking, using recursion or a stack.

Tracking visited nodes is essential to avoid infinite loops in graphs with cycles.

DFS does not guarantee shortest paths; use BFS for shortest path problems in unweighted graphs.

DFS can detect cycles and is useful in many real-world applications like dependency checking and maze solving.

Understanding DFS's internal stack mechanism helps manage recursion limits and implement iterative versions.

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