1
$\begingroup$

I came to know through some examples that DFS and Backtracking aren't exactly the same ( A misconception I had since a long time). So now my question is, since Backtracking visits nodes backwards step by step while DFS on a graph may directly jump some nodes backwards, is DFS a faster algorithm? If so, only in terms of constants or complexity wise?

Edit: Maybe the original writeup was a bit confusing. What I mean specifically is this.

DFS: dfs

A normal implemetation of DFS should traverse the following tree in this manner A->B->C->D. This implies that the implementation for what we normally refer to as DFS visits each node exactly once, giving it a time complexity O(V) where V is the number of vertices.

By Backtracking, what I have in mind is this: backtracking

This I feel is a more bare bones approach where one step of backtracking actually goes to a parent node and explores its other children, instead of skipping over some parent nodes which had only one child (node B here) to begin with. This results in a traversal sequence of A->B->C->B->A->D. This particular example shows that this is always going to require more nodes to be visited than the standard DFS and hence the question.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ As I understand, backtracking is a (meta) algorithm to solve a problem by exploring partial solutions. DFS is an algorithm to traverse a tree or move around a graph. You can see DFS as a particular case of backtracking in which the problem that is being solved is do something with a node (accept it) when all its neighbors have been visited, reject a node if it has been accepted, and visit neighboring nodes in some order. You can also see backtracking as doing DFS on the graph formed by the partial solutions of a problem. $\endgroup$ – plop Aug 11 '20 at 21:33
  • 1
    $\begingroup$ In your question it looks like you have in mind a particular form of backtracking. What is it? $\endgroup$ – plop Aug 11 '20 at 21:34
  • $\begingroup$ DFS is a particular form of backtracking for graph traversal: start from a node and explore as deep as possible before backtracking (i.e. returning to the next neighbour of some previous node). $\endgroup$ – Alexandru Dinu Aug 11 '20 at 21:35
  • $\begingroup$ And whatever you mean, the answer is "In general, NO". To be more specific, it depends on the graph. By backtracking you want to find a node satisfying some conditions. If these nodes are close to the initial node, then BFS will be faster. If they are far and you've picked a lucky branch, then DFS will be faster. $\endgroup$ – user114966 Aug 11 '20 at 21:47
  • $\begingroup$ I'm sorry, I think the original question lacked some clarity. Please see the edited question. $\endgroup$ – Hrishikesh Athalye Aug 12 '20 at 4:20
1
$\begingroup$

When you explore a graph of $N$ vertices and $E$ edges, you basically need to store the visited vertices in a $N$ boolean array. But eventually (when you are interested in retrieving path and not only connection), you will use instead a $N$ bactrack array, containing for each vertex, the one that let you reach it (the parent vertex in the exploration tree).

Exploration methods BFS and DFS needs an extra storage for a queue of vertices to visit which size is $O(N)$. One can consider that the difference between BFS and DFS is just that they respectively use a FIFO and LIFO queue. Note that DFS algorithms often use a recursion hiding the additional storage.

Now, what you call "backtrack" is just a simpler way to do the DFS as you don't have a "todo" queue. When a vertex is fully explore, you just go back in the exploration tree. Of course, it is less efficient than DFS as you will run the exploration loop several times on some vertex. One can argue that it is slightly more efficient in space as you save the queue storage, but practically, this is negligible.

Improve this answer
$\endgroup$
0
$\begingroup$

In DFS also the traversal sequence on the above graph will be A->B->C->B->A->D->A. It is just that it prints a node when it visits it first time and marks it as visited.

In this case, it'll print A B C but when it again visits B and A it ignores it as it is already visited.

Backtracking is a programming paradigm whereas DFS is an actual algorithm that uses backtracking to traverse the tree. Hope that helps.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.