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 (nodes) in a graph by going as deep as possible along each path before backtracking. It starts at a chosen node and visits neighbors one by one, diving deeper until no new nodes are found. This method helps to understand the structure of the graph and find paths or connected parts.

Why it matters

Without DFS, exploring complex networks like social connections, maps, or web links would be slow and confusing. DFS helps computers quickly find routes, check if parts are connected, or detect cycles. It is a foundation for many algorithms that solve real-world problems like puzzle solving, network analysis, and scheduling.

Where it fits

Before learning DFS, you should understand what graphs are and how they represent connections. After DFS, you can learn Breadth First Search (BFS) and advanced graph algorithms like shortest path or cycle detection. DFS is a building block for many graph-related problems.

Mental Model

Core Idea

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

Think of it like...

Imagine exploring a maze by always taking the first unexplored path you see, going as far as possible until hitting a dead end, then stepping back to try other paths.

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

This shows DFS going deep from A to C, then backtracking to explore D.

Build-Up - 7 Steps

1

Foundation

Understanding Graphs and Nodes

Concept: Learn what a graph is and how nodes connect with edges.

A graph is a collection of points called nodes connected by lines called edges. Each node can connect to one or more nodes. Graphs can be directed (edges have direction) or undirected (edges go both ways).

Result

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

Understanding the structure of graphs is essential before exploring them with DFS.

2

Foundation

Representing Graphs in Code

Concept: Learn how to store graphs using adjacency lists.

Graphs are often stored as adjacency lists: each node has a list of neighbors. For example, node 0 connects to nodes 1 and 2, so adjacency_list[0] = [1, 2]. This is memory efficient and easy to use for DFS.

Result

You have a simple way to represent graph connections in code.

Choosing the right graph representation makes traversal algorithms like DFS easier to implement.

3

Intermediate

Basic DFS Algorithm Implementation

🤔Before reading on: do you think DFS uses a queue or a stack to keep track of nodes? Commit to your answer.

Concept: DFS uses a stack (explicit or via recursion) to explore nodes deeply.

DFS starts at a node, marks it visited, then recursively visits each unvisited neighbor. This recursion acts like a stack, remembering where to backtrack.

Result

DFS visits all reachable nodes from the start node, going deep before wide.

Knowing DFS uses a stack helps understand its deep exploration pattern and backtracking.

4

Intermediate

Handling Visited Nodes to Avoid Loops

🤔Before reading on: do you think DFS can get stuck in cycles without tracking visited nodes? Commit to yes or no.

Concept: DFS must track visited nodes to avoid infinite loops in cyclic graphs.

When DFS visits a node, it marks it as visited. If it encounters a visited node again, it skips it. This prevents revisiting the same nodes endlessly.

Result

DFS safely explores graphs with cycles without getting stuck.

Tracking visited nodes is critical to prevent infinite loops and ensure correct traversal.

5

Intermediate

Iterative DFS Using an Explicit Stack

🤔Before reading on: do you think DFS can be done without recursion? Commit to yes or no.

Concept: DFS can be implemented iteratively using a stack data structure instead of recursion.

Instead of recursive calls, use a stack to store nodes to visit. Pop a node, visit it, push its unvisited neighbors. Repeat until stack is empty.

Result

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

Understanding iterative DFS reveals the underlying stack mechanism and helps avoid recursion limits.

6

Advanced

DFS for Detecting Cycles in Graphs

🤔Before reading on: do you think DFS alone can detect cycles, or do you need extra data? Commit to your answer.

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

While visiting nodes, mark them as 'in recursion stack'. If DFS finds a neighbor already in this stack, a cycle exists. Remove nodes from stack when backtracking.

Result

DFS can identify if a graph contains cycles, important for many applications.

Using recursion stack tracking extends DFS from traversal to cycle detection.

7

Expert

DFS Orderings: Preorder, Postorder, and Applications

🤔Before reading on: do you think the order of visiting nodes in DFS matters? Commit to yes or no.

Concept: DFS can record nodes in different orders (preorder, postorder) to solve complex problems.

Preorder records nodes when first visited; postorder records after all descendants are visited. Postorder is used in topological sorting and strongly connected components.

Result

DFS orderings enable advanced graph algorithms beyond simple traversal.

Recognizing DFS orderings unlocks powerful graph algorithms used in real-world systems.

Under the Hood

DFS uses a stack structure to keep track of nodes to visit next. In recursive DFS, the call stack stores the path. Each node is marked visited to avoid repeats. The algorithm explores neighbors deeply before backtracking, ensuring all reachable nodes are visited once.

Why designed this way?

DFS was designed to explore graphs deeply and efficiently using minimal memory. Using recursion or a stack naturally fits the problem of exploring paths fully before trying alternatives. Alternatives like BFS explore breadth first but require queues and more memory for wide graphs.

┌─────────────┐
│ Start Node  │
└──────┬──────┘
       │
       ▼
┌─────────────┐
│ Visit Node  │
│ Mark Visited│
└──────┬──────┘
       │
       ▼
┌─────────────┐
│ For each    │
│ neighbor:   │
│ if unvisited│
│ recurse or  │
│ push to stack│
└──────┬──────┘
       │
       ▼
┌─────────────┐
│ Backtrack   │
│ when no     │
│ neighbors   │
└─────────────┘

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 wrong or inefficient results; BFS or Dijkstra's algorithm are better choices.

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 steps.

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

Why it matters: Not marking visited nodes causes programs to freeze or crash due to infinite recursion or loops.

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

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

Reality: Iterative DFS can be as fast and sometimes more efficient by avoiding recursion overhead and stack limits.

Why it matters: Assuming recursion is always better can cause stack overflow errors in large graphs.

Quick: Does the order of neighbors visited in DFS affect the final traversal? Commit to yes or no.

Common Belief: The order of neighbors does not affect DFS traversal results.

Reality: Neighbor order affects the path DFS takes and the order nodes are visited, which can change outputs in some algorithms.

Why it matters: Ignoring neighbor order can cause confusion when debugging or comparing DFS results.

Expert Zone

1

DFS recursion stack can be used to detect back edges, which indicate cycles in directed graphs.

2

The order of neighbor traversal in DFS can be tuned to optimize for specific problems like lexicographically smallest paths.

3

Iterative DFS requires careful stack management to mimic recursion, especially when tracking postorder or preorder.

When NOT to use

DFS is not suitable when shortest paths are needed; use BFS or Dijkstra instead. For very large or dense graphs, DFS may cause stack overflow or performance issues; iterative methods or specialized algorithms are better.

Production Patterns

DFS is used in compilers for syntax checking, in network analysis to find connected components, and in puzzle solvers like mazes. It is also a base for algorithms like topological sort and strongly connected components detection.

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 wide exploration.

Backtracking Algorithms

DFS is the core mechanism behind backtracking, exploring choices deeply and undoing them.

Knowing DFS clarifies how backtracking systematically searches solution spaces in puzzles and optimization.

Human Problem Solving

DFS mimics how people explore options deeply before reconsidering alternatives.

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

Common Pitfalls

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

Wrong approach:

void dfs(int node) {
printf("%d ", node);
for (int i = 0; i < adj_size[node]; i++) {
int next = adj[node][i];
dfs(next);
}
}

Correct approach:

int visited[MAX];
void dfs(int node) {
if (visited[node]) return;
visited[node] = 1;
printf("%d ", node);
for (int i = 0; i < adj_size[node]; i++) {
int next = adj[node][i];
dfs(next);
}
}

Root cause:

Forgetting to track visited nodes leads to revisiting the same nodes endlessly.

#2 Using DFS to find shortest path without extra logic.

Wrong approach:

void dfs(int node) {
if (node == target) {
printf("Found target");
return;
}
for (int i = 0; i < adj_size[node]; i++) {
dfs(adj[node][i]);
}
}

Correct approach:

Use BFS or Dijkstra's algorithm for shortest path instead of DFS.

Root cause:

Misunderstanding DFS's traversal order as shortest path search.

#3 Recursion depth too large causes stack overflow.

Wrong approach:

void dfs(int node) {
visited[node] = 1;
for (int i = 0; i < adj_size[node]; i++) {
if (!visited[adj[node][i]]) dfs(adj[node][i]);
}
}
// Called on very large graph causing crash

Correct approach:

Use iterative DFS with explicit stack to avoid recursion limits.

Root cause:

Not considering system recursion depth limits in large graphs.

Key Takeaways

DFS explores graphs by going deep along one path before backtracking to explore others.

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

DFS can be implemented recursively or iteratively using a stack, each with pros and cons.

DFS orderings like preorder and postorder enable advanced algorithms like cycle detection and topological sorting.

DFS is not suitable for shortest path problems; use BFS or other algorithms instead.

Practice

1. What is the main idea behind Depth First Search (DFS) on a graph?

easy

A. Visit all nodes at the current depth before moving deeper

B. Visit nodes randomly without any order

C. Explore as far as possible along each branch before backtracking

D. Only visit nodes with no outgoing edges

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 nodes level by level, 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 nodes level-wise
• Assuming DFS visits nodes randomly

2. Which of the following is the correct way to start a DFS function in C for a graph represented by adjacency list adj and visited array visited?

easy

A. void dfs(int node) { visited[node] = 1; for(int i=0; i

B. void dfs(int node) { visited[node] = true; for(int i=0; i

C. void dfs(int node) { visited[node] = 0; for(int i=0; i

D. void dfs(int node) { visited[node] = 1; for(int i=0; i

Solution

1. Step 1: Mark current node as visited

   Set visited[node] = 1 (or true) to avoid revisiting.

2. Step 2: Traverse neighbors only if not visited

   Check if neighbor is unvisited before recursive DFS call to prevent infinite loops.

3. Final Answer:

   void dfs(int node) { visited[node] = 1; for(int i=0; i -> Option D

4. Quick Check:

   Mark visited and check before recursion [OK]

Hint: Always check visited before recursive DFS call [OK]

Common Mistakes:

• Not checking if neighbor is visited
• Using wrong visited value (0 instead of 1)
• Using .size() instead of .length in C arrays

3. Consider the following graph adjacency list:
0: [1, 2]
1: [2]
2: [0, 3]
3: [3]
Starting DFS from node 2, what is the order of nodes visited?

medium

A. [2, 3, 0, 1]

B. [2, 0, 1, 3]

C. [2, 0, 3, 1]

D. [2, 1, 0, 3]

Solution

1. Step 1: Start DFS at node 2

   Visit 2, mark visited. Neighbors: 0 and 3.

2. Step 2: Visit neighbor 0 first

   From 2, go to 0. Visit 0, neighbors: 1 and 2 (2 already visited).

3. Step 3: Visit neighbor 1 from 0

   Visit 1, neighbor: 2 (visited). Backtrack.

4. Step 4: Back to 2, visit neighbor 3

   Visit 3, neighbor: 3 (already visited). End.

5. Final Answer:

   [2, 0, 1, 3] -> Option B

6. Quick Check:

   DFS order from 2 = [2,0,1,3] [OK]

Hint: Follow neighbors depth-first, mark visited to avoid repeats [OK]

Common Mistakes:

• Visiting nodes multiple times
• Visiting neighbors in wrong order
• Ignoring visited checks causing loops

4. The following DFS code has a bug. What is the error?

void dfs(int node) {
  visited[node] = 1;
  for(int i=0; i<adj[node].length; i++) {
    dfs(adj[node][i]);
  }
}

medium

A. Missing check if neighbor is already visited before recursive call

B. Visited array is not initialized

C. Incorrect loop condition syntax

D. Visited[node] should be set after recursion

Solution

1. Step 1: Analyze DFS recursion calls

   The code calls dfs on all neighbors without checking if they are visited.

2. Step 2: Identify risk of infinite recursion

   Without visited check, DFS may revisit nodes endlessly causing stack overflow.

3. Final Answer:

   Missing check if neighbor is already visited before recursive call -> Option A

4. Quick Check:

   Always check visited before recursion [OK]

Hint: Check visited before recursive DFS call to avoid loops [OK]

Common Mistakes:

• Assuming visited check is optional
• Setting visited after recursion
• Ignoring infinite recursion risk

5. Given a directed graph with possible cycles, how can DFS be modified to detect if a cycle exists?

hard

A. Use a recursion stack array to track nodes in the current path and check if a node is revisited in this stack

B. Only mark nodes visited after all neighbors are processed

C. Use BFS instead of DFS to detect cycles

D. Ignore visited array and rely on node values

Solution

1. Step 1: Understand cycle detection in DFS

   Detect cycles by tracking nodes currently in recursion (call) stack.

2. Step 2: Use recursion stack array

   Maintain an array marking nodes in current DFS path; if a neighbor is in this stack, a cycle exists.

3. Step 3: Differentiate from visited array

   Visited marks all visited nodes; recursion stack tracks current path only.

4. Final Answer:

   Use a recursion stack array to track nodes in the current path and check if a node is revisited in this stack -> Option A

5. Quick Check:

   Recursion stack detects cycles in DFS [OK]

Hint: Track recursion stack to find cycles during DFS [OK]

Common Mistakes:

• Confusing visited with recursion stack
• Using BFS for cycle detection in directed graphs
• Not tracking current path nodes