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

Tag: algorithm Author: headphones Date: 2009-08-02

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

Is this Homework?
Even if it is, the answer will only add to understanding. It's not like so many "Do my whole project for me" homework questions...

Best Answer

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.

comments:

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: 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.
@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). :-)

Other Answer1

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.

Other Answer2

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.

Other Answer3

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).

Other Answer4

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.