DFS — Depth-First Search Algorithm Explained

Depth-first search, or DFS, is an algorithm for exploring a tree or graph by following one path as far as possible before backtracking. In plain terms: DFS keeps going deeper until it gets stuck, then it returns to the last place where another branch is available.

If you remember one idea, remember this: DFS means "go deep, then backtrack."

What Depth-First Search Does

DFS can be used on trees and on general graphs. Starting from one node, it repeatedly moves to an unvisited neighbor. When it reaches a node with no unvisited neighbor left, it backtracks to the previous node and continues from there.

That backtracking is the defining behavior. In recursive implementations, the call stack handles it automatically. In iterative implementations, an explicit stack plays the same role.

Why DFS Order Can Change

DFS does not produce one universal visiting order. The exact order depends on the order in which neighbors are considered.

For example, if a node has neighbors $B$ and $C$, visiting $B$ first can give a different DFS order than visiting $C$ first. The search is still DFS in both cases because the rule is the same: keep going deeper before exploring a sibling branch.

DFS Example On A Small Graph

Suppose the graph has these connections:

• $A$ connects to $B$ and $C$
• $B$ connects to $D$ and $E$
• $C$ connects to $F$

Assume we always inspect neighbors from left to right and start at $A$.

DFS proceeds like this:

1. Visit $A$
2. Go to $B$
3. Go to $D$
4. $D$ has no unvisited neighbor, so backtrack to $B$
5. From $B$, go to $E$
6. $E$ is done, so backtrack to $B$, then to $A$
7. From $A$, go to $C$
8. From $C$, go to $F$

So one valid DFS visitation order is:

$$A, B, D, E, C, F$$

The key idea is that DFS finishes the $A \to B$ side before it starts the $A \to C$ side. If you changed the neighbor order, the visitation order could change too.

Why Backtracking Uses A Stack

DFS always needs a way to remember where to return after reaching a dead end. That is why stacks appear naturally in DFS.

In recursive DFS, each function call waits while the search goes deeper, and the program returns in reverse order when it backtracks. In iterative DFS, you push nodes onto a stack and pop them when it is time to continue from the most recent unfinished point.

DFS Time And Space Complexity

If the graph is stored as an adjacency list and each vertex is marked the first time it is visited, DFS runs in

$$O(V + E)$$

time for the reachable part of the graph, where $V$ is the number of vertices and $E$ is the number of edges.

The extra space is typically

$$O(V)$$

because the visited structure and the recursion stack or explicit stack can each grow with the number of vertices.

Common DFS Mistakes

Forgetting To Mark Visited Nodes

In a general graph, forgetting the visited check can make DFS loop through a cycle forever. Even in a tree stored as an undirected graph, you still need to avoid immediately walking back to the parent unless your code handles that case explicitly.

Assuming DFS Finds The Shortest Path

DFS can find a path, but it does not generally guarantee a shortest path in an unweighted graph. If shortest path is the goal and all edges have equal weight, BFS is usually the right starting point.

Treating The DFS Order As Unique

The order depends on the neighbor order. If that order changes, the traversal order can change too.

When Depth-First Search Is Used

DFS is useful when you want to explore structure rather than just nearest distance first. Common uses include:

• checking whether a node is reachable
• finding connected components
• detecting cycles in some graph settings
• traversing trees
• solving backtracking-style problems such as mazes or puzzle search

The main reason it appears so often is that "go deep, then backtrack" matches many recursive problem structures.

DFS Vs BFS: The Practical Difference

DFS goes down a branch first. BFS explores all nodes at one distance before moving to the next distance.

If you care about exhaustive exploration or recursive structure, DFS is often natural. If you care about the shortest path in an unweighted graph, BFS is often the safer first choice.

Try A Similar Traversal

Draw a small graph with six nodes and choose a fixed neighbor order. Run DFS by hand and write down exactly when you move forward and when you backtrack. If your order changes after you reorder the neighbors, that is not a bug. It is part of how DFS works.