DFS Depth First Search on Graph in DSA C# - Deep Dive

Overview - DFS Depth First Search on Graph

What is it?

Depth First Search (DFS) is a way to explore all the points (called nodes) in a graph by going as deep as possible along each path before backtracking. Imagine starting at one node and visiting neighbors by diving down one path fully before trying another. This method helps find paths, check connections, and explore structures in graphs.

Why it matters

Without DFS, it would be hard to explore complex networks like social connections, maps, or web links efficiently. DFS helps solve problems like finding if two points are connected, detecting cycles, or ordering tasks. Without it, computers would waste time checking every possible path randomly, making many tasks slow or impossible.

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 searches like Breadth First Search (BFS), shortest path algorithms, and graph traversal optimizations.

Mental Model

Core Idea

DFS explores a graph by going deep along one path until it can't go further, then backtracks to explore other paths.

Think of it like...

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

Graph example:

  A
 / \
B   C
|   |
D - E

DFS starting at A:
A -> B -> D -> E -> C

Traversal path:
A
│
├─> B
│   │
│   └─> D
│       │
│       └─> E
│           └─> C

Build-Up - 7 Steps

1

Foundation

Understanding Graphs and Nodes

Concept: Graphs are collections of points called nodes connected by lines called edges.

A graph is like a network of places connected by roads. Each place is a node, and each road is an edge. Graphs can be directed (one-way roads) or undirected (two-way roads). We represent graphs using lists or maps showing which nodes connect to which.

Result

You can picture a graph as a map of connected points, ready to be explored.

Understanding what a graph is and how nodes connect is essential before learning how to explore it.

2

Foundation

What is Depth First Search (DFS)?

Concept: DFS is a method to visit all nodes in a graph by going deep along one path before backtracking.

Imagine standing at a node. You pick one neighbor and move there, then pick a neighbor of that neighbor, and so on, until you reach a node with no unvisited neighbors. Then you go back to the previous node and try other neighbors. This way, you explore all nodes by diving deep first.

Result

You get a path that visits every node reachable from the start, exploring deeply before moving sideways.

Knowing DFS explores deeply first helps you predict the order nodes are visited.

3

Intermediate

Implementing DFS with Recursion

🤔Before reading on: Do you think DFS can be done without loops, using only function calls? Commit to yes or no.

Concept: DFS can be implemented using a function that calls itself to explore neighbors, called recursion.

In C#, we write a function that visits a node, marks it visited, then calls itself for each unvisited neighbor. This way, the function stack keeps track of where we are, automatically handling backtracking.

Result

The program visits nodes in depth-first order, printing or processing each node once.

Understanding recursion as a natural way to explore deeply simplifies DFS implementation and mirrors the mental model.

4

Intermediate

Using a Stack for Iterative DFS

🤔Before reading on: Can DFS be done without recursion? Commit to yes or no.

Concept: DFS can also be done using a stack data structure to remember nodes to visit next, avoiding recursion.

Instead of calling a function repeatedly, we use a stack to store nodes. We pop a node, visit it, then push its unvisited neighbors onto the stack. This simulates the call stack used in recursion.

Result

The iterative DFS visits nodes in the same order as recursive DFS but uses explicit stack management.

Knowing DFS can be iterative helps when recursion is limited or when you want more control over the process.

5

Intermediate

Handling Cycles and Visited Nodes

🤔Before reading on: What happens if DFS visits a node twice in a graph with cycles? Commit to your answer.

Concept: To avoid infinite loops in graphs with cycles, DFS must track which nodes have been visited.

We keep a set or array marking nodes as visited when first explored. Before visiting a neighbor, we check if it is already visited. This prevents revisiting nodes and endless loops.

Result

DFS completes without getting stuck, visiting each node once.

Tracking visited nodes is critical to safely explore graphs with cycles and ensures correctness.

6

Advanced

DFS Applications: Detecting Cycles and Connectivity

🤔Before reading on: Can DFS alone tell if a graph has a cycle? Commit to yes or no.

Concept: DFS can be used to detect cycles and check if all nodes are connected by analyzing the traversal path and visited nodes.

By tracking the recursion stack or parent nodes during DFS, we can detect if we revisit a node still in the current path, indicating a cycle. Also, if DFS visits all nodes from a start node, the graph is connected.

Result

You can find cycles and connectivity status using DFS traversal.

Understanding how DFS traversal order reveals graph properties unlocks powerful graph analysis techniques.

7

Expert

Optimizing DFS for Large Graphs and Memory

🤔Before reading on: Does DFS always use the same amount of memory regardless of graph size? Commit to yes or no.

Concept: DFS memory use depends on graph depth and structure; optimizing data structures and traversal order can improve performance.

In very deep or large graphs, recursion can cause stack overflow. Using iterative DFS with an explicit stack avoids this. Also, ordering neighbors or pruning paths can reduce unnecessary exploration. Efficient visited tracking (bitsets, arrays) saves memory.

Result

DFS runs efficiently on large graphs without crashing or wasting resources.

Knowing DFS memory behavior and optimization techniques is essential for real-world large graph problems.

Under the Hood

DFS uses a stack structure, either the program call stack in recursion or an explicit stack in iteration, to remember nodes to explore next. When a node is visited, it is marked to avoid revisiting. The algorithm explores neighbors deeply by pushing them onto the stack and backtracks when no unvisited neighbors remain. This process continues until all reachable nodes are visited.

Why designed this way?

DFS was designed to explore graphs efficiently by focusing on depth first, which simplifies path finding and cycle detection. Using recursion or a stack matches natural problem structure and allows easy backtracking. Alternatives like BFS explore breadth first but are less suited for deep path exploration. DFS's simplicity and power made it a foundational graph algorithm.

DFS internal flow:

Start Node
   │
   ▼
[Visit Node]
   │
   ▼
[Mark Visited]
   │
   ▼
[Push Neighbors]
   │
   ▼
[Pop Next Node]
   │
   ├─> If unvisited: Repeat
   └─> If no nodes left: End

Myth Busters - 4 Common Misconceptions

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

Common Belief: DFS always finds the shortest path between nodes because it explores deeply.

Reality: DFS does not guarantee the shortest path; it explores one path fully before trying others, which can be longer.

Why it matters: Using DFS for shortest path can lead to incorrect or inefficient results; algorithms like BFS or Dijkstra are needed for shortest paths.

Quick: Can DFS be used on graphs with cycles without any special handling? Commit to yes or no.

Common Belief: DFS works fine on any graph without extra checks.

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

Why it matters: Failing to track visited nodes causes programs to hang or crash, making DFS unusable on real graphs.

Quick: Is recursive DFS always better than iterative DFS? Commit to yes or no.

Common Belief: Recursive DFS is always simpler and better than iterative DFS.

Reality: Recursive DFS can cause stack overflow on deep graphs; iterative DFS avoids this by managing its own stack.

Why it matters: Choosing recursive DFS blindly can cause crashes in large graphs; knowing iterative DFS is safer is important.

Quick: Does DFS visit nodes in the same order every time regardless of neighbor order? Commit to yes or no.

Common Belief: DFS visits nodes in a fixed order no matter how neighbors are arranged.

Reality: DFS visit order depends on the order neighbors are checked; different neighbor orders produce different traversal paths.

Why it matters: Assuming fixed order can cause bugs in algorithms relying on specific traversal sequences.

Expert Zone

1

DFS traversal order can be controlled by sorting neighbors, which affects algorithms like topological sort or cycle detection.

2

In directed graphs, DFS can be used to find strongly connected components by combining with low-link values (Tarjan's algorithm).

3

The recursion stack in DFS can be used to detect back edges, which indicate cycles, a subtle but powerful insight.

When NOT to use

DFS is not suitable when you need the shortest path in unweighted graphs; use BFS instead. For weighted graphs, use Dijkstra or A*. Also, DFS can be inefficient on very wide graphs where breadth exploration is better.

Production Patterns

DFS is used in compilers for syntax checking, in network analysis for connectivity, in puzzle solving like mazes, and in AI for exploring game states. Iterative DFS with explicit stacks is preferred in production to avoid recursion limits.

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 level order traversal.

Backtracking Algorithms

DFS is the foundation of backtracking, exploring choices deeply and undoing them when needed.

Knowing DFS clarifies how backtracking systematically explores all possibilities in puzzles and constraint problems.

Human Problem Solving

DFS mirrors how people explore options deeply before reconsidering alternatives.

Recognizing DFS in human thinking helps design algorithms that mimic natural exploration and decision-making.

Common Pitfalls

#1 Infinite loop due to revisiting nodes in cyclic graphs.

Wrong approach:

void DFS(int node) {
Console.WriteLine(node);
foreach (var neighbor in graph[node]) {
DFS(neighbor);
}
}

Correct approach:

bool[] visited = new bool[graph.Length];
void DFS(int node) {
if (visited[node]) return;
visited[node] = true;
Console.WriteLine(node);
foreach (var neighbor in graph[node]) {
DFS(neighbor);
}
}

Root cause:

Not marking nodes as visited causes repeated visits and infinite recursion in cycles.

#2 Stack overflow from deep recursion on large graphs.

Wrong approach:

Recursive DFS without limits on very deep graphs causes crash.

Correct approach:

Use iterative DFS with a stack:
Stack stack = new Stack();
stack.Push(startNode);
while (stack.Count > 0) {
int node = stack.Pop();
if (!visited[node]) {
visited[node] = true;
Console.WriteLine(node);
foreach (var neighbor in graph[node]) {
stack.Push(neighbor);
}
}
}

Root cause:

Recursion depth exceeds system limits; iterative approach avoids this.

#3 Assuming DFS finds shortest paths in unweighted graphs.

Wrong approach:

Using DFS to find shortest path:
DFS(start);
// Take first found path as shortest

Correct approach:

Use BFS for shortest path:
Queue queue = new Queue();
queue.Enqueue(start);
// Track distances and parents for shortest path

Root cause:

DFS explores deeply without considering path length, so it may find longer paths first.

Key Takeaways

Depth First Search explores graphs by going as deep as possible 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 or other algorithms for that purpose.

Iterative DFS is safer for large graphs to prevent stack overflow from deep recursion.

DFS is a foundation for many graph algorithms and problem-solving techniques like cycle detection and backtracking.

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 until all are visited

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 with other traversal methods

   BFS visits neighbors first, but DFS goes deep first.

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 traversal in C# using recursion on a graph represented by adjacency list Dictionary<int, List<int>> graph?

easy

A. void DFS(int node, HashSet<int> visited) { if (visited.Contains(node)) return; visited.Add(node); foreach (var neighbor in graph[node]) DFS(neighbor, visited); }

B. void DFS(int node) { visited.Add(node); foreach (var neighbor in graph[node]) DFS(neighbor); }

C. void DFS(int node, List<int> visited) { if (visited.Contains(node)) return; visited.Add(node); foreach (var neighbor in graph[node]) DFS(neighbor, visited); }

D. void DFS(int node, HashSet<int> visited) { visited.Add(node); foreach (var neighbor in graph) DFS(neighbor, visited); }

Solution

1. Step 1: Check parameters and visited tracking

   void DFS(int node, HashSet<int> visited) { if (visited.Contains(node)) return; visited.Add(node); foreach (var neighbor in graph[node]) DFS(neighbor, visited); } uses HashSet to track visited nodes and prevents revisiting.

2. Step 2: Verify iteration over neighbors

   void DFS(int node, HashSet<int> visited) { if (visited.Contains(node)) return; visited.Add(node); foreach (var neighbor in graph[node]) DFS(neighbor, visited); } correctly iterates over neighbors of the current node from the graph dictionary.

3. Final Answer:

   void DFS(int node, HashSet<int> visited) { if (visited.Contains(node)) return; visited.Add(node); foreach (var neighbor in graph[node]) DFS(neighbor, visited); } -> Option A

4. Quick Check:

   Correct recursion with visited check [OK]

Hint: Use HashSet to track visited nodes in DFS recursion [OK]

Common Mistakes:

• Not checking if node is visited before recursion
• Using List instead of HashSet for visited (slow lookup)
• Iterating over graph keys instead of neighbors

3. Given the graph adjacency list:

var graph = new Dictionary {
  {1, new List<int>{2, 3}},
  {2, new List<int>{4}},
  {3, new List<int>{4}},
  {4, new List<int>()}
};

List<int> visited = new List<int>();
DFS(1, visited); // DFS as defined in option C above
Console.WriteLine(string.Join(", ", visited));

What is the output?

medium

A. 1, 2, 3, 4

B. 1, 2, 4, 3

C. 1, 3, 4, 2

D. 1, 4, 2, 3

Solution

1. Step 1: Start DFS from node 1

   Visit 1, mark visited. Neighbors: 2, 3.

2. Step 2: Visit neighbor 2 first

   Visit 2, then its neighbor 4. 4 has no neighbors, backtrack.

3. Step 3: Backtrack to 1 and visit neighbor 3

   Visit 3, then neighbor 4 (already visited, skip).

4. Step 4: Order of visited nodes

   Visited nodes in order: 1, 2, 4, 3.

5. Final Answer:

   1, 2, 4, 3 -> Option B

6. Quick Check:

   DFS order = 1,2,4,3 [OK]

Hint: DFS visits neighbors in order, backtracks after deepest node [OK]

Common Mistakes:

• Assuming BFS order instead of DFS
• Visiting node 3 before node 2
• Revisiting already visited nodes

4. Consider this DFS code snippet in C#:

void DFS(int node, HashSet<int> visited) {
  visited.Add(node);
  foreach (var neighbor in graph.Keys) {
    if (!visited.Contains(neighbor)) {
      DFS(neighbor, visited);
    }
  }
}

What is the main problem with this DFS implementation?

medium

A. It iterates over all graph nodes instead of neighbors of the current node

B. It does not add the current node to visited

C. It uses List instead of HashSet for visited nodes

D. It does not check if the node is null before recursion

Solution

1. Step 1: Analyze the foreach loop

   The loop iterates over all keys in the graph, not neighbors of the current node.

2. Step 2: Understand DFS neighbor traversal

   DFS should explore neighbors of the current node, not all nodes in the graph.

3. Final Answer:

   It iterates over all graph nodes instead of neighbors of the current node -> Option A

4. Quick Check:

   DFS must visit neighbors, not all nodes [OK]

Hint: Loop over neighbors, not all graph keys [OK]

Common Mistakes:

• Looping over graph.Keys instead of graph[node]
• Forgetting to add node to visited
• Not checking visited before recursion

5. You want to find if there is a path from node 1 to node 5 in this directed graph:

var graph = new Dictionary {
  {1, new List<int>{2, 3}},
  {2, new List<int>{4}},
  {3, new List<int>{4, 5}},
  {4, new List<int>{}},
  {5, new List<int>{}}
};

bool DFS(int current, int target, HashSet<int> visited) {
  if (current == target) return true;
  visited.Add(current);
  foreach (var neighbor in graph[current]) {
    if (!visited.Contains(neighbor)) {
      if (DFS(neighbor, target, visited)) return true;
    }
  }
  return false;
}

var visited = new HashSet<int>();
bool result = DFS(1, 5, visited);
Console.WriteLine(result);

What will be printed?

hard

A. Runtime exception

B. False

C. Compilation error

D. True

Solution

1. Step 1: Start DFS from node 1 looking for 5

   Visit 1, neighbors 2 and 3.

2. Step 2: Explore neighbor 2

   From 2, visit 4. 4 has no neighbors, backtrack.

3. Step 3: Explore neighbor 3

   From 3, neighbors are 4 and 5. 4 visited, then 5 found matches target.

4. Step 4: DFS returns true when target found

   DFS returns true and prints True.

5. Final Answer:

   True -> Option D

6. Quick Check:

   Path exists from 1 to 5 [OK]

Hint: DFS returns true immediately when target found [OK]

Common Mistakes:

• Assuming no path because 5 is not direct neighbor
• Not returning true when target found
• Forgetting to mark visited nodes