Why should you care?
In the previous Graphs article, we learned how graphs represent relationships between objects.
But storing a graph is only the beginning.
A common question is:
How do we actually explore everything inside a graph?
This is where Depth-First Search, commonly called DFS, comes in.
DFS is used in:
- Graph traversal
- Tree traversal
- Finding connected components
- Detecting cycles
- Maze solving
- Path finding
- Topological sorting
- Dependency analysis
- Backtracking algorithms
- Network exploration
DFS is especially important because it teaches a fundamental algorithmic pattern:
Go as deep as possible before going back.
The Problem
Suppose we have this graph:
```text id="c9qv8j"
A
/ \
B C
/ \ \
D E F
We want to visit every node.
Where should we start?
If we simply move from one node to another without a strategy, we could:
* Visit nodes multiple times.
* Get stuck in cycles.
* Miss parts of the graph.
* Waste computation.
We need a systematic traversal algorithm.
Two of the most important graph traversal algorithms are:
```text id="v5h0mt"
BFS → Breadth-First Search
DFS → Depth-First Search
DFS explores one path deeply before returning and exploring another.
The Concept
The basic DFS process is:
```text id="t0w8w8"
Start at a node
↓
Visit it
↓
Choose an unvisited neighbor
↓
Visit that neighbor
↓
Continue deeper
↓
No unvisited neighbors?
↓
Go back
↓
Continue another path
The "go back" operation is called **backtracking**.
DFS can be implemented using:
1. **Recursion**
2. **An explicit Stack**
This is an important connection:
```text id="4b9lqa"
DFS
↓
Stack
Recursion itself uses the call stack internally.
Simple Explanation
Consider:
```text id="k1x3d6"
A
/ \
B C
/ \
D E
Start at `A`.
DFS visits:
```text id="b5sl4n"
A
Then goes deeper:
```text id="yx3h85"
A → B
Then deeper again:
```text id="1e6hlc"
A → B → D
D has no unvisited neighbors.
So we go back:
```text id="zpjx5k"
A → B
Then explore:
```text id="1c6dgt"
A → B → E
After finishing B, return to A.
Then explore:
```text id="2t5z99"
A → C
A possible traversal order is:
```text id="n76w4n"
A → B → D → E → C
The exact order depends on how neighbors are stored.
The important part is the strategy:
Go deep first.
Real-world Analogy
Imagine exploring a maze.
You enter through the starting point.
Instead of exploring every nearby corridor first, you:
- Choose one corridor.
- Keep walking forward.
- Continue until you reach a dead end.
- Walk backward to the last decision point.
- Try another unexplored corridor.
- Repeat.
That is DFS.
Visually:
```text id="h3l2cu"
Start
↓
Path 1
↓
Path 1.1
↓
Path 1.1.1
↓
Dead end
↓
Backtrack
↓
Path 1.2
This is exactly how DFS explores a graph.
---
## Code Example
Let's implement DFS recursively in Java.
Suppose our graph is represented using an adjacency list:
```java id="k4os65"
Map<String, List<String>> graph = new HashMap<>();
graph.put("A", Arrays.asList("B", "C"));
graph.put("B", Arrays.asList("A", "D", "E"));
graph.put("C", Arrays.asList("A"));
graph.put("D", Arrays.asList("B"));
graph.put("E", Arrays.asList("B"));
Now implement DFS:
```java id="j3z9n8"
public static void dfs(
String node,
Map> graph,
Set visited) {
visited.add(node);
System.out.println(node);
for (String neighbor : graph.get(node)) {
if (!visited.contains(neighbor)) {
dfs(neighbor, graph, visited);
}
}
}
Call it using:
```java id="j5s6da"
Set<String> visited = new HashSet<>();
dfs("A", graph, visited);
A possible output:
```text id="lq98x4"
A
B
D
E
C
---
## Understanding the Code
The first important line is:
```java id="6l1q7k"
visited.add(node);
We mark the current node as visited.
Why?
Because graphs can contain cycles.
For example:
```text id="m5l1kd"
A → B
↑ ↓
└───C
If we don't remember which nodes we've visited, DFS could keep going:
```text id="7v6vpy"
A → B → C → A → B → C → ...
forever.
The visited set prevents this.
Exploring Neighbors
Then:
```java id="w6ydx9"
for (String neighbor : graph.get(node)) {
we examine every neighboring node.
If we haven't visited it:
```java id="jz0m7c"
if (!visited.contains(neighbor)) {
we recursively explore it:
```java id="y5yk5b"
dfs(neighbor, graph, visited);
This is the key line.
It tells DFS:
> "Don't just visit the neighbor. Go all the way down that path."
---
## The Call Stack
DFS recursion becomes much easier to understand when you visualize the call stack.
Suppose:
```text id="zw8ks8"
A → B → D
DFS does:
```text id="a3cnz7"
dfs(A)
↓
dfs(B)
↓
dfs(D)
The call stack becomes:
```text id="h2m4xz"
┌─────────┐
│ dfs(D) │
├─────────┤
│ dfs(B) │
├─────────┤
│ dfs(A) │
└─────────┘
When D has no more neighbors:
```text id="m3j4bw"
dfs(D)
returns.
Then:
```text id="5r2jpb"
dfs(B)
continues.
This is exactly the backtracking behavior of DFS.
Iterative DFS Using a Stack
DFS doesn't have to use recursion.
We can explicitly create a stack.
```java id="g65g4e"
public static void dfsIterative(
String start,
Map> graph) {
Set<String> visited = new HashSet<>();
Stack<String> stack = new Stack<>();
stack.push(start);
while (!stack.isEmpty()) {
String node = stack.pop();
if (visited.contains(node)) {
continue;
}
visited.add(node);
System.out.println(node);
for (String neighbor : graph.get(node)) {
if (!visited.contains(neighbor)) {
stack.push(neighbor);
}
}
}
}
The important difference is:
```text id="w2d5lq"
Recursive DFS
↓
Uses call stack
Iterative DFS
↓
Uses explicit stack
The underlying idea is the same.
DFS on a Tree
DFS isn't limited to graphs.
Trees can also be traversed using DFS.
Consider:
```text id="3b2t4y"
A
/ \
B C
/ \
D E
There are three classic DFS tree traversals.
### Preorder
```text id="6b7b8b"
Root
Left
Right
Result:
```text id="b9n0m8"
A B D E C
### Inorder
```text id="ap5o5k"
Left
Root
Right
Result:
```text id="g4efh0"
D B E A C
This is especially important for Binary Search Trees because inorder traversal produces values in sorted order.
### Postorder
```text id="0q8x9n"
Left
Right
Root
Result:
```text id="5z2fda"
D E B C A
All three are forms of **Depth-First Traversal**.
---
## Time Complexity
For a graph represented using an adjacency list:
```text id="j8y0on"
O(V + E)
where:
```text id="oq8t3u"
V = number of vertices
E = number of edges
Why?
DFS visits every reachable vertex at most once:
```text id="1y1ujv"
O(V)
It also examines the edges:
```text id="j5xk1y"
O(E)
Therefore:
```text id="7lhqym"
O(V + E)
This is one of the fundamental graph algorithm complexities.
Space Complexity
DFS requires:
```text id="b8xk5g"
Visited set → O(V)
The recursion stack can also grow to:
```text id="x9s2cm"
O(V)
in the worst case.
Therefore, recursive DFS generally uses:
```text id="w0r7bn"
O(V)
additional space.
Iterative DFS also requires:
```text id="e9ay4n"
O(V)
for the stack and visited set in the worst case.
Common Mistakes
Mistake 1: Forgetting the visited set
This is one of the most dangerous DFS mistakes.
Consider:
```text id="spzgjq"
A → B
↑ ↓
└───C
Without `visited`, DFS can repeatedly follow:
```text id="q8rj1u"
A → B → C → A → B → C → ...
Always track visited nodes when traversing a general graph.
Mistake 2: Marking nodes too late
A common mistake is marking a node as visited only after recursively exploring its neighbors.
That can cause the same node to be added to the recursion path multiple times in graphs with cycles or converging paths.
A safe general pattern is:
```java id="8zv0f5"
visited.add(node);
for (...) {
if (!visited.contains(neighbor)) {
dfs(...);
}
}
Mark the node when you begin processing it.
---
### Mistake 3: Thinking DFS always finds the shortest path
DFS finds a path if one exists, but it does **not** generally find the shortest path in an unweighted graph.
For shortest paths in an unweighted graph, **BFS** is usually the appropriate algorithm.
For example:
```text id="l4qlpi"
A ─── B ─── D
\ /
└── C ───
DFS may explore a longer route before discovering a shorter one.
DFS and BFS solve different traversal problems.
Mistake 4: Assuming DFS has one fixed traversal order
Consider:
```text id="f5v2dl"
A
├── B
└── C
DFS could produce:
```text id="xkz5l4"
A B C
or:
```text id="d5h7u0"
A C B
depending on neighbor ordering.
The DFS strategy remains the same.
The exact traversal order depends on the graph representation.
---
### Mistake 5: Ignoring recursion depth
A graph can contain a very long chain:
```text id="k9h2sd"
A
↓
B
↓
C
↓
D
↓
...
Recursive DFS may create a very deep call stack.
For sufficiently large graphs, an iterative implementation with an explicit stack can avoid recursion-depth limitations.
Advanced Notes
1. DFS for Cycle Detection
DFS can detect cycles.
For an undirected graph, one approach is to keep track of the parent node.
For directed graphs, we can track the current recursion path.
For example:
```text id="6e2q2m"
A → B → C
↑ ↓
└─────
DFS eventually encounters a node that is already part of the current recursion path.
That indicates a cycle.
Cycle detection is useful for:
* Dependency systems
* Build systems
* Scheduling
* Graph validation
---
### 2. Connected Components
Suppose a graph contains:
```text id="b5k6ub"
A ─ B ─ C
D ─ E
F
There are three connected components:
```text id="3fs0a1"
{A, B, C}
{D, E}
{F}
We can run DFS from every unvisited node.
Each DFS identifies one connected component.
This is a common graph problem.
---
### 3. Topological Sorting
DFS can also be used for **topological sorting** of a Directed Acyclic Graph.
For example:
```text id="r7i4a8"
Requirements
↓
Programming
↓
Data Structures
↓
Algorithms
DFS can explore dependencies and add nodes after their descendants have been processed.
Reversing that finishing order gives a topological ordering.
This is useful for:
- Course prerequisites
- Build dependencies
- Task scheduling
- Package dependencies
4. Backtracking
DFS is closely related to backtracking.
The general pattern is:
```text id="7k7w9q"
Choose
↓
Explore
↓
Valid?
↓
Continue
↓
Dead end?
↓
Undo
↓
Try another choice
This appears in problems such as:
* Maze solving
* Sudoku
* N-Queens
* Permutations
* Combinations
* Path finding
The key idea is that DFS provides the exploration mechanism while backtracking provides the "undo and try another option" behavior.
---
### 5. DFS vs BFS
This is one of the most important comparisons to understand.
| Feature | DFS | BFS |
| --------------------------------- | --------------------------------- | ---------------------- |
| Main structure | Stack | Queue |
| Strategy | Go deep | Go wide |
| Typical implementation | Recursion / Stack | Queue |
| Shortest path in unweighted graph | Not guaranteed | Yes |
| Memory | Can be O(V) | Can be O(V) |
| Useful for | Exploration, cycles, backtracking | Shortest paths, levels |
Think:
```text id="u3l8mw"
DFS → Deep first
BFS → Broad first
The Bigger Picture
DFS connects almost everything we've learned so far.
Stack
DFS is naturally implemented using a stack.
```text id="2vq5bi"
DFS
↓
Stack
Recursion provides an implicit stack.
---
### Trees
Tree traversals such as:
```text id="7d8o2k"
Preorder
Inorder
Postorder
are DFS-based traversals.
Graphs
DFS provides a systematic way to explore graphs.
```text id="j1q9cp"
Graph
↓
DFS
↓
Traversal
---
### Recursion
Recursive DFS repeatedly solves the same problem on a neighboring node:
```text id="z8g4ds"
dfs(current)
↓
dfs(neighbor)
↓
dfs(next neighbor)
Big-O
From our Big-O article:
```text id="l2xw6h"
DFS → O(V + E)
This gives us a way to reason about how graph traversal scales.
---
### Binary Search and Sorting
Binary Search and sorting algorithms taught us how algorithms reduce problems into smaller pieces.
DFS applies a similar recursive mindset:
```text id="g1j8qt"
Current problem
↓
Choose neighbor
↓
Solve smaller exploration problem
↓
Return
↓
Explore next neighbor
The Most Important Mental Model
Don't think of DFS as:
"An algorithm that visits nodes."
Think:
"Keep going forward until you can't, then backtrack."
Visualize:
```text id="u3e9ro"
A
/ \
B C
/ \
D E
DFS:
```text id="q9azj7"
A
↓
B
↓
D
↑
B
↓
E
↑
B
↑
A
↓
C
The arrows going down represent exploration.
The arrows going up represent backtracking.
That is DFS.
Summary
Depth-First Search is a graph traversal algorithm that explores as deeply as possible before backtracking.
The basic process is:
```text id="2y7b0p"
Visit node
↓
Choose unvisited neighbor
↓
Go deeper
↓
Dead end?
↓
Backtrack
↓
Explore another path
Key points:
* DFS explores deeply before moving to another branch.
* It can be implemented recursively or with a stack.
* A `visited` set prevents repeated exploration and infinite loops.
* DFS on an adjacency-list graph takes `O(V + E)`.
* Recursive DFS can use `O(V)` stack space.
* DFS does not generally guarantee the shortest path.
* It is useful for cycle detection, connected components, topological sorting, and backtracking.
* Tree preorder, inorder, and postorder traversals are DFS-based.
* BFS is the natural alternative when you need level-by-level exploration or shortest paths in an unweighted graph.
The core relationship is:
```text id="w3p4cr"
DFS
↓
Go deep
↓
Stack
↓
Backtrack
Top comments (0)