DFS, short for Depth First Search, is an algorithm of searching tree or graph data structures. It starts at the root (or selecting some node as the root in the case of graph), and explores as far (or deep) as possible until it cannot go any further, then it backtracks and tries other paths.
DFS is always implemented using recursion. Its non-recursive implementation depends on an explicit stack.1
2
3
4
5
6
7
8
9
10
11// Node represents a node in a graph
void dfs(Node node) {
if (qualified(node) || !canGoFuther(node)) {
return;
}
for (Node neighbor : getNeighbors(node)) {
if (canBeProcessed(neighbor)) {
dfs(neighbor);
}
}
}
I have applied DFS to varieties of search problems in previous posts, e.g. problems relating to binary tree, and problems relating to graph. So I won’t cover the same problems in this post, but I’ll write about the topic DFS vs. backtracking which I find both interesting and confusing.
DFS vs. Backtracking
I thought DFS and backtracking were the same thing. It was not until I prepared for this post that I realized I was wrong.
After reading what I can find on the Internet, my opinion is:
- They are both search algorithms
- They both backtrack when they cannot explore any further
- DFS is limited to the domain of tree or graph, but backtracking has a broader application domain
- DFS backtracks when it encounters the tree leaves or the ending of a path in the graph, but backtracking backtracks when it finds out that the current path down will lead to nothing. In other words, DFS explores all the nodes and checks all the possibilities until it finds the answer, which sounds like brutal-force search; backtracking does not waste time on the possibilities leading to naught (kind of like pruning), so it is more efficient.