173

What's the difference between backtracking and depth first search?

0

17 Answers 17

139

Backtracking is a more general purpose algorithm.

Depth-First search is a specific form of backtracking related to searching tree structures. From Wikipedia:

One starts at the root (selecting some node as the root in the graph case) and explores as far as possible along each branch before backtracking.

It uses backtracking as part of its means of working with a tree, but is limited to a tree structure.

Backtracking, though, can be used on any type of structure where portions of the domain can be eliminated - whether or not it is a logical tree. The Wiki example uses a chessboard and a specific problem - you can look at a specific move, and eliminate it, then backtrack to the next possible move, eliminate it, etc.

6
  • 32
    Responding to an ancient post here. Good answer, but... couldn't the chessboard problem be represented as a tree also? :-) From any position on a chessboard for a given piece, is there not a tree of possible moves extending into the future? Part of me feels like any case where backtracking could be used, could also be modeled as a tree, but I'm not sure if I'm correct in that intuition.
    – The111
    Jun 18, 2013 at 23:52
  • 8
    @The111: Indeed, any search problem can be represented as a tree -- you have a node for each possible partial solution, and an edge from each node to the one or more possible alternative choices that could be made at this state. I think lcn's answer, that backtracking usually means DFS on the (usually implicit) search tree generated during recursion, comes closest to the truth. Jul 27, 2013 at 2:44
  • 7
    @j_random_hacker So, a DFS is a way to explore a tree (or graph more generally), while backtracking is a way to solve a problem (which employs a DFS along with pruning). :-)
    – The111
    Jul 27, 2013 at 3:52
  • Confusingly, Wikipedia describes backtracking as a depth-first search algorithm, apparently conflating these two concepts. Jul 12, 2018 at 18:11
  • A good explanation! It is really helpful.
    – Zhou Haibo
    Mar 2, 2021 at 4:39
45

I think this answer to another related question offers more insights.

For me, the difference between backtracking and DFS is that backtracking handles an implicit tree and DFS deals with an explicit one. This seems trivial, but it means a lot. When the search space of a problem is visited by backtracking, the implicit tree gets traversed and pruned in the middle of it. Yet for DFS, the tree/graph it deals with is explicitly constructed and unacceptable cases have already been thrown, i.e. pruned, away before any search is done.

So, backtracking is DFS for implicit tree, while DFS is backtracking without pruning.

3
  • 2
    I think it's confusing to think of backtracking as handling an implicit tree. When I first read this I agreed but digging deeper I realized the "implicit tree" is really.. the recursion tree.. Take any example that uses backtracking, like permuting a string of characters, there is no logical tree (no implicit tree) whatsoever regarding to the problem but we do have a recursion tree that models the incremental string building process. As for pruning, that's the pruning done to the recursion tree where a total brute force is performed... (to be continued)
    – Gang Fang
    Aug 22, 2019 at 2:53
  • 1
    (continued) E.g. print all permutation of "answer" string and let say the 3rd char has to be character "a". The first 2 level of the recursion tree obey O(n!) but at the 3rd level all branch except those that are appending "a" are pruned (backtracked).
    – Gang Fang
    Aug 22, 2019 at 2:57
  • @GangFang agreed, I like pointing out that it is usually a recursion tree. Even though I guess it's a conceptual tree of solution space, I don't know of a situation where recursion isn't used to create that solution space
    – yoyodunno
    Feb 23, 2022 at 4:58
29

IMHO, most of the answers are either largely imprecise and/or without any reference to verify. So let me share a very clear explanation with a reference.

First, DFS is a general graph traversal (and search) algorithm. So it can be applied to any graph (or even forest). Tree is a special kind of Graph, so DFS works for tree as well. In essence, let’s stop saying it works only for a tree, or the likes.

Based on [1], Backtracking is a special kind of DFS used mainly for space (memory) saving. The distinction that I’m about to mention may seem confusing since in Graph algorithms of such kind we’re so used to having adjacency list representations and using iterative pattern for visiting all immediate neighbors (for tree it is the immediate children) of a node, we often ignore that a bad implementation of get_all_immediate_neighbors may cause a difference in memory uses of the underlying algorithm.

Further, if a graph node has branching factor b, and diameter h (for a tree this is the tree height), if we store all immediate neighbors at each steps of visiting a node, memory requirements will be big-O(bh). However, if we take only a single (immediate) neighbor at a time and expand it, then the memory complexity reduces to big-O(h). While the former kind of implementation is termed as DFS, the latter kind is called Backtracking.

Now you see, if you’re working with high level languages, most likely you’re actually using Backtracking in the guise of DFS. Moreover, keeping track of visited nodes for a very large problem set could be really memory intensive; calling for a careful design of get_all_immediate_neighbors (or algorithms that can handle revisiting a node without getting into infinite loops).

[1] Stuart Russell and Peter Norvig, Artificial Intelligence: A Modern Approach, 3rd Ed

1
  • 1
    +1 Totally agree. Both lcn, Reed, and so on referred DFS as a tree search algorithm, which is too narrow (if not wrong) and is misleading to beginners.
    – Eric
    Jun 8, 2022 at 15:47
21

According to Donald Knuth, it's the same. Here is the link on his paper about the Dancing Links algorithm, which is used to solve such "non-tree" problems as N-queens and Sudoku solver.

Backtracking, also called depth-first search

1
  • 4
    Mentioned in page 1 of the linked pdf. Apr 29, 2020 at 23:10
19

Backtracking is usually implemented as DFS plus search pruning. You traverse search space tree depth-first constructing partial solutions along the way. Brute-force DFS can construct all search outcomes, even the ones, that do not make sense practically. This can be also very inefficient to construct all solutions (n! or 2^n). So in reality as you do DFS, you need to also prune partial solutions, which do not make sense in context of the actual task, and focus on the partial solutions, which can lead to valid optimal solutions. This is the actual backtracking technique - you discard partial solutions as early as possible, make a step back and try to find local optimum again.

Nothing stops to traverse search space tree using BFS and execute backtracking strategy along the way, but it doesn't make sense in practice because you would need to store search state layer by layer in the queue, and tree width grows exponentially to the height, so we would waste a lot of space very quickly. That's why trees are usually traversed using DFS. In this case search state is stored in the stack (call stack or explicit structure) and it can't exceed tree height.

10

Usually, a depth-first-search is a way of iterating through an actual graph/tree structure looking for a value, whereas backtracking is iterating through a problem space looking for a solution. Backtracking is a more general algorithm that doesn't necessarily even relate to trees.

6

I would say, DFS is the special form of backtracking; backtracking is the general form of DFS.

If we extend DFS to general problems, we can call it backtracking. If we use backtracking to tree/graph related problems, we can call it DFS.

They carry the same idea in algorithmic aspect.

1
  • The relation between DFS and Backtracking is, in fact, just the converse. Check my response which details this.
    – KGhatak
    Nov 23, 2019 at 10:28
6

DFS describes the way in which you want to explore or traverse a graph. It focuses on the concept of going as deep as possible given the choice.

Backtracking, while usually implemented via DFS, focuses more on the concept of pruning unpromising search subspaces as early as possible.

5

The way I look at DFS vs. Backtracking is that backtracking is much more powerful. DFS helps me answer whether a node exists in a tree, while backtracking can help me answer all paths between 2 nodes.

Note the difference: DFS visits a node and marks it as visited since we are primarily searching, so seeing things once is sufficient. Backtracking visits a node multiple times as it's a course correction, hence the name backtracking.

Most backtracking problems involve:

def dfs(node, visited):
  visited.add(node)
  for child in node.children:
    dfs(child, visited)
  visited.remove(node) # this is the key difference that enables course correction and makes your dfs a backtracking recursion.
1
  • this is a great observation!
    – J.W.
    Jul 14, 2022 at 12:03
4

IMO, on any specific node of the backtracking, you try to depth firstly branching into each of its children, but before you branch into any of the child node, you need to "wipe out" previous child's state(this step is equivalent to back walk to the parent node). In other words, each siblings state should not impact each other.

On the contrary, during normal DFS algorithm, you don't usually have this constraint, you don't need to wipe out(back track) previous siblings state in order to construct next sibling node.

2

Depth first is an algorithm for traversing or searching a tree. See here. Backtracking is a much more broad term that is used whereever a solution candidate is formed and later discarded by backtracking to a former state. See here. Depth first search uses backtracking to search a branch first (solution candidate) and if not successful search the other branch(es).

2

Depth first search(DFS) and backtracking are different searching and traversing algorithms. DFS is more broad and is used in both graph and tree data structure while DFS is limited to tree. With that being said,it does not mean DFS can't be used in graph. It is used in graph as well but only produce spanning tree, a tree without loop(multiple edge starting and ending at same vertex). That is why it is limited to tree.
Now coming back to backtracking, DFS use backtracking algorithm in tree data structure so in tree, DFS and backtracking are similar.
Thus,we can say, they are in same in tree data structure whereas in graph data structure, they are not same.

1

Idea - Start from any point, check if its the desired endpoint, if yes then we found a solution else goes to all next possible positions and if we can't go further then return to the previous position and look for other alternatives marking that current path wont lead us to the solution.

Now backtracking and DFS are 2 different names given to the same idea applied on 2 different abstract data types.

If the idea is applied on matrix data structure we call it backtracking.

If the same idea is applied on tree or graph then we call it DFS.

The cliche here is that a matrix could be converted to a graph and a graph could be transformed to a matrix. So, we actually apply the idea. If on a graph then we call it DFS and if on a matrix then we call it backtracking.

The idea in both of the algorithm is same.

1

Backtracking is just depth first search with specific termination conditions.

Consider walking through a maze where for each step you make a decision, that decision is a call to the call stack (which conducts your depth first search)... if you reach the end, you can return your path. However, if you reach a deadend, you want to return out of a certain decision, in essence returning out of a function on your call stack.

So when I think of backtracking I care about

  1. State
  2. Decisions
  3. Base Cases (Termination Conditions)

I explain it in my video on backtracking here.

An analysis of backtracking code is below. In this backtracking code I want all of the combinations that will result in a certain sum or target. Therefore, I have 3 decisions which make calls to my call stack, at each decision I either can pick a number as part of my path to reach the target num, skip that number, or pick it and pick it again. And then if I reach a termination condition, my backtracking step is just to return. Returning is the backtracking step because it gets out of that call on the call stack.

class Solution:    

"""

Approach: Backtracking 

State
    -candidates 
    -index 
    -target 

Decisions
    -pick one --> call func changing state: index + 1, target - candidates[index], path + [candidates[index]]
    -pick one again --> call func changing state: index, target - candidates[index], path + [candidates[index]]
    -skip one --> call func changing state: index + 1, target, path

Base Cases (Termination Conditions)
    -if target == 0 and path not in ret
        append path to ret
    -if target < 0: 
        return # backtrack 

"""

def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
    """
    @desc find all unique combos summing to target
    @args
        @arg1 candidates, list of ints
        @arg2 target, an int
    @ret ret, list of lists 
    """
    if not candidates or min(candidates) > target: return []

    ret = []
    self.dfs(candidates, 0, target, [], ret)
    return ret 

def dfs(self, nums, index, target, path, ret):
    if target == 0 and path not in ret: 
        ret.append(path)
        return #backtracking 
    elif target < 0 or index >= len(nums): 
        return #backtracking 


    # for i in range(index, len(nums)): 
    #     self.dfs(nums, i, target-nums[i], path+[nums[i]], ret)

    pick_one = self.dfs(nums, index + 1, target - nums[index], path + [nums[index]], ret)
    pick_one_again = self.dfs(nums, index, target - nums[index], path + [nums[index]], ret)
    skip_one = self.dfs(nums, index + 1, target, path, ret)
1

In my opinion, the difference is pruning of tree. Backtracking can stop (finish) searching certain branch in the middle by checking the given conditions (if the condition is not met). However, in DFS, you have to reach to the leaf node of the branch to figure out if the condition is met or not, so you cannot stop searching certain branch until you reach to its leaf nodes.

0

In a depth-first search, you start at the root of the tree and then explore as far along each branch, then you backtrack to each subsequent parent node and traverse it's children

Backtracking is a generalised term for starting at the end of a goal, and incrementally moving backwards, gradually building a solution.

2
  • 8
    Backtracking does not mean to start at the end and move backwards. It keeps a log of visited nodes to backtrack if a dead end is found. Feb 16, 2017 at 23:17
  • 1
    "starting at the end ...", huh!!
    – 7kemZmani
    Feb 26, 2017 at 4:39
0

The difference is: Backtracking is a concept of how an algorithm works, DFS (depth first search) is an actual algorithm that bases on backtracking. DFS essentially is backtracking (it is searching a tree using backtracking) but not every algorithm based on backtracking is DFS.

To add a comparison: Backtracking is a concept like divide and conqueror. QuickSort would be an algorithm based on the concept of divide and conqueror.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.