1. Introduction
In this tutorial, we’ll explore the difference between backtracking and depth-first search. We’ll also look at an example algorithm using the backtracking technique.
2. Depth-First Search
Depth-first search (DFS) is the algorithm used to traverse a graph. It starts on the root node and travels as deep as possible along each branch.
The tree below presents the order in which nodes will be visited when applying depth-first search:
We can use the depth-first search to solve puzzles with only one solution or to find connected components. It’s also a default algorithm for finding cycles in a graph. Moreover, it’s a more useful general graph search than the breadth-first search because it’s more space-efficient.
3. Backtracking
Backtracking is an algorithm used to iterate over all possible solutions in the search space. Therefore, it’s commonly used to solve problems with constraints. In this sense, backtracking limits the search space, thus saving compute time.
The process of constructing partial solutions from the base case corresponds to performing a depth search traversal of the tree.
3.1. An Example
Let’s write a straightforward algorithm to generate all subsets from elements in the given array. For each input element, we will add it to the candidate list and recursively invoke the Subsets() function. After this step, we backtrack by removing this element from our candidate list. Finally, we call Subsets() function again. The ultimate result is a sum of both recursive calls.
The recursive execution tree of the above algorithm will look as follows:
We can find the final solution at the bottom of the execution tree. It’s a set of eight elements:
The subsets order shows that to construct them, we used depth-first search following the left tree branch.
3.2. Applications of Backtracking
Backtracking is widely used to solve crosswords, Sudoku, chess, tic-tac-toe, and other puzzles. It’s also useful when generating all the combinations of elements from a given set. Additionally, it’s the basis of programming languages such as Icon, Planner, and Prolog.
4. Comparison
Interestingly, we can see that the solution space over which the backtracking algorithm iterates usually has a form of a graph. As such, the implementation of both algorithms is very similar:
5. Conclusion
In this article, we discussed the similarities and differences between backtracking and DFS. We also wrote a simple algorithm using backtracking.
Finally, we learned that because backtracking uses DFS to traverse the solution space, they can both be represented as recursive algorithms.