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-&gt;B-&gt;C-&gt;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-&gt;B-&gt;C-&gt;B-&gt;A-&gt;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.
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 &quot;backtrack&quot; is just a simpler way to do the DFS as you don't have a &quot;todo&quot; 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.