DFS Depth First Search on Graph in DSA Java - 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, going deeper until you cannot go further, then stepping back to explore other paths. 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 is crucial for tasks like finding routes, detecting cycles, or checking if parts are connected.

Where it fits

Before learning DFS, you should understand what graphs are and how they represent connections between points. After DFS, you can learn Breadth First Search (BFS) for a different exploration style, and then move on to graph algorithms like shortest path or cycle detection.

Mental Model

Core Idea

DFS explores a graph by going as far as possible down one path before backtracking to explore others.

Think of it like...

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

Start
  ↓
Node A
  ↓
Node B
  ↓
Node C (dead end)
  ↑
Backtrack to B
  ↓
Node D
  ↓
... (repeat)

Graph traversal path:
A -> B -> C -> back to B -> D -> ...

Build-Up - 7 Steps

1

Foundation

Understanding Graphs and Nodes

Concept: Graphs are made of nodes (points) connected by edges (lines).

A graph is a collection of nodes connected by edges. Each node can connect to one or more nodes. Graphs can be directed (edges have direction) or undirected (edges go both ways). For example, a social network where people are nodes and friendships are edges.

Result

You can picture a graph as dots connected by lines, representing relationships or connections.

Understanding what graphs are is essential because DFS works by moving through these connections step-by-step.

2

Foundation

What is Depth First Search (DFS)?

Concept: DFS is a method to visit all nodes by exploring as deep as possible before backtracking.

Starting from a node, DFS visits a neighbor, then a neighbor of that neighbor, and so on until no new nodes are found. Then it backtracks to explore other neighbors. This ensures every node reachable from the start is visited once.

Result

DFS produces a path that goes deep into the graph before stepping back to explore other branches.

Knowing DFS explores deeply first helps you predict how it will traverse complex graphs.

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 recursive function calls that explore neighbors one by one.

In recursion, the function calls itself for each unvisited neighbor. It marks nodes as visited to avoid repeats. When no neighbors remain, the function returns, backtracking to previous calls. Example Java code: void dfs(int node, boolean[] visited, List> graph) { visited[node] = true; System.out.print(node + " -> "); for (int neighbor : graph.get(node)) { if (!visited[neighbor]) { dfs(neighbor, visited, graph); } } }

Result

The output prints nodes in the order they are visited, showing the deep-first path.

Understanding recursion as a natural way to explore deep paths simplifies DFS implementation and reasoning.

4

Intermediate

Using a Stack for Iterative DFS

🤔Before reading on: do you think DFS requires recursion, or can it be done with a stack? Commit to your answer.

Concept: DFS can also be done without recursion by using a stack to track nodes to visit next.

Instead of recursive calls, use a stack data structure. Push the start node, then repeatedly pop a node, visit it, and push its unvisited neighbors. This simulates the call stack of recursion. Example Java code: void dfsIterative(int start, List> graph) { boolean[] visited = new boolean[graph.size()]; Stack stack = new Stack<>(); stack.push(start); while (!stack.isEmpty()) { int node = stack.pop(); if (!visited[node]) { visited[node] = true; System.out.print(node + " -> "); for (int neighbor : graph.get(node)) { if (!visited[neighbor]) { stack.push(neighbor); } } } } }

Result

The output prints nodes in DFS order without using recursion.

Knowing DFS can be iterative helps in environments where recursion depth is limited or to understand the underlying process.

5

Intermediate

Handling Cycles and Visited Nodes

🤔Before reading on: do you think DFS can get stuck in loops if we don't track visited nodes? Commit yes or no.

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

Graphs can have cycles where nodes connect back to earlier nodes. Without marking visited nodes, DFS would revisit the same nodes endlessly. Using a boolean visited array or set prevents this by skipping already visited nodes.

Result

DFS completes without infinite loops, visiting each node once.

Recognizing the need for visited tracking prevents bugs and infinite loops in real graph traversal.

6

Advanced

DFS Applications: Connected Components and Cycle Detection

🤔Before reading on: do you think DFS can help find if a graph is all in one piece or split? Commit yes or no.

Concept: DFS can find connected parts of a graph and detect cycles by exploring nodes and their neighbors carefully.

By running DFS from unvisited nodes repeatedly, you can count how many connected groups exist. For cycle detection, DFS tracks nodes in the current path (recursion stack). If a neighbor is already in the current path, a cycle exists. Example: Detect cycle in directed graph using recursion stack tracking.

Result

You can identify separate connected groups and detect cycles efficiently.

Understanding these applications shows DFS is not just traversal but a powerful tool for graph analysis.

7

Expert

DFS Orderings: Preorder, Postorder, and Topological Sort

🤔Before reading on: do you think the order DFS visits nodes can be used to sort tasks? Commit yes or no.

Concept: DFS visit orderings can be used to solve complex problems like ordering tasks with dependencies (topological sort).

DFS can record nodes when first visited (preorder) or after all neighbors are visited (postorder). Postorder is key for topological sorting in directed acyclic graphs (DAGs), where tasks must be done in order. By pushing nodes onto a stack after visiting neighbors, popping the stack gives a valid task order. Example: Topological sort using DFS postorder.

Result

DFS helps produce a valid order of tasks respecting dependencies.

Knowing DFS orderings unlocks advanced graph algorithms essential in scheduling and dependency resolution.

Under the Hood

DFS uses a stack structure, either implicitly via recursion or explicitly, to remember nodes to visit next. It marks nodes as visited to avoid repeats. The call stack or explicit stack stores the path being explored, allowing backtracking when dead ends are reached. This process ensures all reachable nodes are visited exactly once.

Why designed this way?

DFS was designed to explore graphs deeply before breadth to efficiently find paths and detect structures like cycles. Using recursion or a stack matches natural problem-solving approaches and fits well with computer memory models. Alternatives like BFS explore breadth first but are less suited for deep path exploration.

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

Myth Busters - 4 Common Misconceptions

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

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

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

Why it matters: Using DFS for shortest path can lead to inefficient or incorrect results; BFS or Dijkstra's algorithm are better choices.

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

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

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

Why it matters: Failing to mark visited nodes causes programs to hang or crash, wasting time and resources.

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

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

Reality: Iterative DFS can be equally efficient and avoids stack overflow risks in deep graphs.

Why it matters: Choosing recursion blindly can cause crashes on large graphs; iterative DFS is safer in production.

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

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

Reality: DFS visit order depends on the order neighbors are stored and accessed in the graph structure.

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

Expert Zone

1

DFS traversal order can change dramatically based on neighbor ordering, affecting algorithms like topological sort or cycle detection.

2

Recursive DFS uses the call stack which can lead to stack overflow on very deep or large graphs; iterative DFS with an explicit stack avoids this.

3

In directed graphs, DFS can be used to find strongly connected components by combining forward and reverse traversals (Tarjan's or Kosaraju's algorithms).

When NOT to use

DFS is not suitable when shortest paths are needed; use BFS or Dijkstra's algorithm instead. For very large graphs with limited memory, iterative DFS or specialized graph traversal methods may be better. Also, DFS is less efficient for finding shortest paths in weighted graphs.

Production Patterns

DFS is used in compilers for syntax checking, in network analysis to find connected components, in puzzle solving (like mazes), and in scheduling tasks with dependencies via topological sorting. It is also foundational in algorithms detecting cycles and strongly connected components in graphs.

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.

Recursion in Programming

DFS often uses recursion to explore nodes deeply.

Mastering recursion clarifies how DFS naturally fits into function call stacks and backtracking.

Human Problem Solving

DFS mimics how people explore options deeply before backtracking.

Recognizing this connection helps understand DFS as a natural search strategy beyond computers.

Common Pitfalls

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

Wrong approach:

void dfs(int node, List> graph) {
System.out.print(node + " -> ");
for (int neighbor : graph.get(node)) {
dfs(neighbor, graph);
}
}

Correct approach:

void dfs(int node, boolean[] visited, List> graph) {
if (visited[node]) return;
visited[node] = true;
System.out.print(node + " -> ");
for (int neighbor : graph.get(node)) {
dfs(neighbor, visited, graph);
}
}

Root cause:

Forgetting to track visited nodes shows misunderstanding of graph cycles and traversal safety.

#2 Using DFS to find shortest path leads to wrong answers.

Wrong approach:

Run DFS and return the first path found as shortest without checking others.

Correct approach:

Use BFS or Dijkstra's algorithm to find shortest paths reliably.

Root cause:

Confusing DFS's deep search with shortest path logic causes incorrect assumptions.

#3 Assuming DFS visit order is fixed regardless of graph data structure.

Wrong approach:

Expecting DFS to visit nodes in numerical order without sorting neighbors.

Correct approach:

Sort or order neighbors explicitly if a specific visit order is required.

Root cause:

Not realizing that neighbor iteration order affects traversal sequence.

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 visit orderings enable advanced algorithms like topological sorting and cycle detection.

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. Randomly visit nodes until all are visited

B. Visit all neighbors of a node before moving deeper

C. Visit nodes in order of their distance from the start node

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

Solution

1. Step 1: Understand DFS traversal

   DFS explores a graph by going deep into one branch before backtracking to explore other branches.

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 D

4. Quick Check:

   DFS = deep exploration first [OK]

Hint: DFS goes deep first, BFS goes wide first [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 from node 0 in Java using recursion?

easy

A. dfs(0, visited, graph);

B. DFS(visited, graph, 0);

C. dfs(graph, 0, visited);

D. dfs(visited, 0, graph);

Solution

1. Step 1: Identify typical DFS method signature

   Common DFS signature is dfs(currentNode, visitedArray, graph).

2. Step 2: Match options to this signature

   dfs(0, visited, graph); matches the order: node, visited, graph. Others have wrong parameter order.

3. Final Answer:

   dfs(0, visited, graph); -> Option A

4. Quick Check:

   Correct parameter order = dfs(node, visited, graph) [OK]

Hint: DFS method usually starts with node, visited, graph [OK]

Common Mistakes:

• Mixing parameter order
• Using uppercase method name 'DFS'
• Passing graph before node

3. Given the graph adjacency list: graph = {{1, 2}, {0, 3}, {0}, {1}} and starting DFS from node 0, what is the order of nodes visited?

medium

A. [0, 1, 3, 2]

B. [0, 2, 1, 3]

C. [0, 1, 2, 3]

D. [0, 3, 1, 2]

Solution

1. Step 1: Start DFS at node 0 and visit neighbors

   From 0, neighbors are 1 and 2. DFS visits 1 first (assuming adjacency order).

2. Step 2: From node 1, visit its neighbors

   Neighbors of 1 are 0 (visited) and 3. Visit 3 next.

3. Step 3: Backtrack and visit remaining neighbors

   After 3, backtrack to 0 and visit 2.

4. Final Answer:

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

5. Quick Check:

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

Hint: Follow neighbors deeply in adjacency order [OK]

Common Mistakes:

• Visiting neighbors in wrong order
• Not backtracking correctly
• Confusing BFS order with DFS

4. What is wrong with this DFS code snippet in Java?

void dfs(int node, boolean[] visited, List<Integer>[] graph) {
  visited[node] = true;
  for (int neighbor : graph[node]) {
    if (visited[neighbor]) {
      dfs(neighbor, visited, graph);
    }
  }
}

medium

A. It does not mark nodes as visited

B. It calls dfs on already visited neighbors causing infinite recursion

C. It uses wrong data types for graph

D. It misses the base case for recursion

Solution

1. Step 1: Check visited condition before recursive call

   The code calls dfs(neighbor) only if visited[neighbor] is true, which means already visited.

2. Step 2: Identify the problem caused

   This causes infinite recursion because it revisits nodes already visited instead of skipping them.

3. Final Answer:

   It calls dfs on already visited neighbors causing infinite recursion -> Option B

4. Quick Check:

   Call dfs only if neighbor not visited [OK]

Hint: Call dfs only if neighbor is NOT visited [OK]

Common Mistakes:

• Calling dfs on visited nodes
• Forgetting to mark visited nodes
• Incorrect loop over neighbors

5. You want to find if there is a path between node 0 and node 4 in this graph:

graph = {{1, 2}, {0, 3}, {0, 4}, {1}, {2}}

Which DFS approach correctly determines if node 4 is reachable from node 0?

hard

A. Run DFS from 4, stop and return true if node 0 is found during traversal

B. Run DFS from 0 and count all visited nodes without checking for 4

C. Run DFS from 0, stop and return true if node 4 is found during traversal

D. Run DFS from 0 but skip node 2 to avoid cycles

Solution

1. Step 1: Understand the goal

   We want to check if node 4 is reachable from node 0, so start DFS at 0.

2. Step 2: Use DFS to find target node

   During DFS, if node 4 is found, stop and return true immediately.

3. Step 3: Evaluate options

   Run DFS from 0, stop and return true if node 4 is found during traversal matches this approach. Run DFS from 4, stop and return true if node 0 is found during traversal starts from wrong node. Run DFS from 0 and count all visited nodes without checking for 4 ignores target. Run DFS from 0 but skip node 2 to avoid cycles skips nodes incorrectly.

4. Final Answer:

   Run DFS from 0, stop and return true if node 4 is found during traversal -> Option C

5. Quick Check:

   DFS from start, stop on target found [OK]

Hint: Stop DFS early when target node is found [OK]

Common Mistakes:

• Starting DFS from wrong node
• Not checking for target during traversal
• Skipping nodes that are part of path