Depth-first search (DFS) is a fundamental algorithm for traversing or searching tree or graph data structures. It starts at a root node (or an arbitrary node in a graph) and explores as far as possible along each branch before backtracking. DFS is widely used in computer science for tasks such as topological sorting, cycle detection, solving puzzles (e.g., mazes), and as a building block for more complex graph algorithms. Its behavior is often contrasted with breadth-first search (BFS), and it can be implemented recursively or iteratively using an explicit stack.
1 Algorithm description
1.1 Basic procedure
The basic procedure of DFS is as follows: begin at a chosen starting node (the root in a tree, or any node in a graph). Mark the node as visited. Then, for each neighbor of that node that has not yet been visited, recursively apply the same process. If the current node has no unvisited neighbors, backtrack to the previous node and continue with its remaining unvisited neighbors. The algorithm terminates when all nodes reachable from the start node have been visited.
1.2 Recursive implementation
A recursive implementation of DFS uses the system call stack implicitly. The function takes a node, marks it visited, and then calls itself on each unvisited neighbor in turn. This approach is concise and naturally mirrors the backtracking process. Pseudocode:
DFS(node):
mark node as visited
for each neighbor of node:
if neighbor is not visited:
DFS(neighbor)1.3 Iterative implementation using a stack
An iterative implementation of DFS uses an explicit stack data structure. The algorithm pushes the starting node onto a stack. While the stack is not empty, it pops a node; if that node has not been visited, it marks it as visited and pushes all its unvisited neighbors onto the stack. The order of pushing determines the traversal order. Pseudocode:
DFS_iterative(start):
stack = new Stack()
stack.push(start)
while stack is not empty:
node = stack.pop()
if node is not visited:
mark node as visited
for each neighbor of node:
if neighbor is not visited:
stack.push(neighbor)1.4 Example walkthrough
Consider an undirected graph with nodes A, B, C, D, and edges A–B, A–C, B–D, C–D. Starting from A, DFS may visit A, then B, then D, then backtrack to B, then to A, then visit C, then D (but D is already visited), and finish. The order of visits depends on the neighbor order. The iterative stack version would produce a similar but potentially different order because of LIFO behavior.
2 Properties
2.1 Time complexity
2.1.1 Adjacency list representation
For a graph with V vertices and E edges stored in an adjacency list, each vertex is visited once, and each edge is examined once (twice for undirected graphs, once per direction). The total time is O(V + E).
2.1.2 Adjacency matrix representation
For an adjacency matrix of size V × V, checking all neighbors of a vertex requires scanning the entire row, taking O(V) time per vertex. Thus total time is O(V²).
2.2 Space complexity
In the worst case, DFS may need to store up to V vertices on the recursion stack (or explicit stack). In the iterative version, the stack can also hold up to V vertices. The visited array requires O(V) space. Therefore, space complexity is O(V) (or O(V + E) if graph is stored separately).
2.3 Completeness and optimality
DFS is complete for finite graphs: it will eventually visit all reachable nodes. For infinite graphs, DFS may get stuck on an infinite branch and never find a goal node. DFS is not optimal: it does not guarantee finding the shortest path, as it follows a path to its full depth before considering alternatives.
3 Variations
3.1 Preorder, inorder, and postorder traversal (for trees)
When DFS is applied to a binary tree, three typical orderings emerge:
- Preorder: visit root, then left subtree, then right subtree.
- Inorder: visit left subtree, then root, then right subtree.
- Postorder: visit left subtree, then right subtree, then root.
These traversal orders correspond to different ways of processing nodes and are especially useful in expression trees, binary search tree operations, and recursive algorithms.
3.2 Directed graph DFS
In directed graphs, DFS explores edges in their given direction. It can classify edges into four types.
3.2.1 Edge classification (tree, back, forward, cross edges)
During DFS on a directed graph, an edge from u to v is classified as:
- Tree edge: if v is first discovered from u.
- Back edge: if v is an ancestor of u in the DFS tree (indicates a cycle).
- Forward edge: if v is a descendant of u but not a tree edge.
- Cross edge: if v is neither ancestor nor descendant (connects different branches).
This classification is crucial for cycle detection and topological sorting.
3.3 Undirected graph DFS
For an undirected graph, every edge is either a tree edge or a back edge (forward and cross edges do not occur because the graph is symmetric). Back edges in undirected graphs also indicate cycles.
3.4 Depth-limited search
Depth-limited search (DLS) is a variant of DFS where a maximum depth limit L is imposed. The algorithm stops exploring a branch once the depth exceeds L. This prevents infinite loops in infinite graphs and can improve memory usage. DLS is incomplete if the goal lies deeper than L, but it can be used as a building block for iterative deepening.
3.5 Iterative deepening depth-first search (IDDFS)
Iterative deepening depth-first search (IDDFS) combines DFS’s space efficiency with BFS’s completeness and optimality (for unweighted graphs). It repeatedly applies depth-limited search with increasing depth limits (0, 1, 2, ...). IDDFS visits nodes multiple times but overall has time complexity O(V + E) for most practical purposes, and space complexity O(V). It is commonly used in game tree search and AI problem solving.
4 Applications
4.1 Topological sorting
A topological ordering of a directed acyclic graph (DAG) can be obtained by performing a postorder DFS. After visiting all descendants of a node, that node is placed on a stack; the final stack order (reversed) gives a topological sort. This is used in scheduling, build systems, and dependency resolution.
4.2 Strongly connected components (Kosaraju’s and Tarjan’s algorithms)
DFS is fundamental to finding strongly connected components (SCCs) in directed graphs. Kosaraju’s algorithm uses two DFS passes (one on the original graph, one on the reversed graph). Tarjan’s algorithm performs a single DFS and uses low‑link values to identify SCCs. These techniques are applied in compiler optimizations, social network analysis, and program analysis.
4.3 Cycle detection in graphs
DFS can detect cycles in both directed and undirected graphs. For directed graphs, the presence of a back edge (during DFS) indicates a cycle. For undirected graphs, a back edge (to an already visited node that is not the parent) indicates a cycle. This is used in deadlock detection, circuit analysis, and validation of tree structures.
4.4 Solving puzzles and pathfinding (e.g., mazes)
DFS is a natural algorithm for exploring mazes: follow a path until a dead end, then backtrack. It can be used to find any path from start to exit, but not necessarily the shortest. It also forms the basis for backtracking algorithms in puzzles like Sudoku, the eight queens problem, and constraint satisfaction.
4.5 Generating spanning trees and forests
Running DFS on a connected undirected graph produces a spanning tree (the tree edges). If the graph is disconnected, DFS forms a spanning forest. This property is used in network routing protocols (e.g., spanning tree protocol for Ethernet bridges).
4.6 Biconnected components and articulation points
DFS can identify articulation points (cut vertices) and biconnected components in an undirected graph. By tracking the discovery time and low-link values, an algorithm (based on Tarjan’s DFS) can find vertices whose removal disconnects the graph. This is important in network reliability analysis and graph drawing.
5 Comparison with other search algorithms
5.1 Breadth-first search (BFS)
BFS explores a graph level by level using a queue, while DFS explores depth first. BFS guarantees the shortest path in unweighted graphs, but uses more memory (O(V) in the worst case, similar to DFS, but BFS typically stores a larger frontier). DFS uses less memory per node in practice when a deep branch is unlikely. BFS is complete and optimal for unweighted graphs; DFS is not optimal.
5.2 Best-first search and A*
Best-first search and A* are heuristic search algorithms that use a priority queue to order nodes based on an evaluation function. They are informed methods, unlike DFS which is uninformed. While DFS can be used for pathfinding, A* typically finds shorter paths with the help of heuristics. DFS is simpler and requires no heuristic, but may miss optimal solutions.
5.3 Uniform-cost search
Uniform-cost search (Dijkstra’s algorithm for single-source) expands nodes in order of increasing path cost. It is complete and optimal for non‑negative edge weights. DFS does not consider path costs and may find a costly path first. Uniform-cost search uses a priority queue and has higher asymptotic complexity than DFS for unweighted graphs.
6 Implementations in programming languages
6.1 Python
A recursive implementation in Python:
def dfs(graph, node, visited=None):
if visited is None:
visited = set()
if node not in visited:
visited.add(node)
for neighbor in graph[node]:
dfs(graph, neighbor, visited)
return visitedAn iterative version using a list as a stack:
def dfs_iterative(graph, start):
visited = set()
stack = [start]
while stack:
node = stack.pop()
if node not in visited:
visited.add(node)
stack.extend(graph[node] - visited)
return visited6.2 C++
Recursive implementation:
#include <vector>
#include <unordered_set>
using namespace std;
void dfs(const vector<vector<int>>& graph, int node, unordered_set<int>& visited) {
if (visited.find(node) == visited.end()) {
visited.insert(node);
for (int neighbor : graph[node]) {
dfs(graph, neighbor, visited);
}
}
}Iterative using the stack container:
#include <stack>
#include <unordered_set>
vector<int> dfs_iterative(const vector<vector<int>>& graph, int start) {
unordered_set<int> visited;
stack<int> st;
st.push(start);
vector<int> result;
while (!st.empty()) {
int node = st.top(); st.pop();
if (visited.find(node) == visited.end()) {
visited.insert(node);
result.push_back(node);
for (int neighbor : graph[node]) {
if (visited.find(neighbor) == visited.end())
st.push(neighbor);
}
}
}
return result;
}6.3 Java
Recursive example:
import java.util.*;
public class DFS {
public static void dfs(Map<Integer, List<Integer>> graph, int node, Set<Integer> visited) {
if (!visited.contains(node)) {
visited.add(node);
for (int neighbor : graph.getOrDefault(node, Collections.emptyList())) {
dfs(graph, neighbor, visited);
}
}
}
}Iterative using Deque:
public static List<Integer> dfsIterative(Map<Integer, List<Integer>> graph, int start) {
Set<Integer> visited = new HashSet<>();
Deque<Integer> stack = new ArrayDeque<>();
stack.push(start);
List<Integer> result = new ArrayList<>();
while (!stack.isEmpty()) {
int node = stack.pop();
if (!visited.contains(node)) {
visited.add(node);
result.add(node);
for (int neighbor : graph.getOrDefault(node, Collections.emptyList())) {
if (!visited.contains(neighbor))
stack.push(neighbor);
}
}
}
return result;
}6.4 JavaScript
Recursive version:
function dfs(graph, node, visited = new Set()) {
if (!visited.has(node)) {
visited.add(node);
for (let neighbor of graph[node]) {
dfs(graph, neighbor, visited);
}
}
return visited;
}Iterative using an array as a stack:
function dfsIterative(graph, start) {
const visited = new Set();
const stack = [start];
while (stack.length) {
const node = stack.pop();
if (!visited.has(node)) {
visited.add(node);
for (let neighbor of graph[node]) {
if (!visited.has(neighbor)) stack.push(neighbor);
}
}
}
return visited;
}7 Common pitfalls and optimizations
7.1 Handling cycles (visited set)
Without a mechanism to track visited nodes, DFS can enter infinite loops on cyclic graphs. Using a visited set (or marking nodes) prevents revisiting the same node. For directed graphs, a separate “on‑stack” flag may be needed to detect cycles in topological sorting.
7.2 Stack overflow in recursion (deep graphs)
Recursive DFS on a deep graph (e.g., a long path of 10⁵ nodes) can cause stack overflow due to excessive recursion depth. The iterative stack implementation avoids this issue. Alternatively, the recursion limit can be increased (e.g., sys.setrecursionlimit in Python), but this is not always portable.
7.3 Memory usage trade-offs
DFS uses O(V) space for the stack in the worst case (e.g., a straight line graph). For graphs with high branching factors, the stack may remain small if the search goes deep. BFS, in contrast, may store up to O(V) nodes in its queue for a balanced tree. Choosing between recursive and iterative implementations should consider system call stack size limitations vs. explicit stack overhead. For very large graphs, memory can be further optimized by using bit‑packed visited arrays or bloom filters for approximate traversal.