# Does DFS have better constants/complexity than Backtracking on a Graph?

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:

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:

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.

• 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. – plop Aug 11 '20 at 21:33
• In your question it looks like you have in mind a particular form of backtracking. What is it? – plop Aug 11 '20 at 21:34
• 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). – Alexandru Dinu Aug 11 '20 at 21:35
• 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. – user114966 Aug 11 '20 at 21:47
• I'm sorry, I think the original question lacked some clarity. Please see the edited question. – Hrishikesh Athalye Aug 12 '20 at 4:20

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.