Does DFS have better constants/complexity than Backtracking on a Graph?
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.