dfs与回溯算法_dfs和回溯法的区别

1，区别不在于回溯，因为dfs也会回溯，而是dfs会将已经访问过的点标记为不可再次连接,不会再撤销，从而使得可搜索路径越来越少，而回溯会在访问初标记，回溯时撤销。使用邻接链表的dfs的时间复杂度为V+E
2，如果在寻径中保留stack, 我们会发现dfs只会找到一条a到b的路径，而回溯法可以找到所有的。注意visit的顺序和stack的顺序不一样.

具体可见例子1：https://codingcompetitions.withgoogle.com/codejam/round/0000000000051705/00000000000881da
中Attempt 3 - Apr 7 2019, 18:27 与 Attempt 1 - Apr 7 2019, 17:57 的区别，仅仅在于Attempt 3加入了visit控制，结果不再超时。而attempt1的回溯算法之所以完全没有用visit控制，也能完成功能，是因为此图的路径方向特殊，否则会因为环路而形成无限循环。

2的例子：
https://codingcompetitions.withgoogle.com/codejam/round/0000000000051635/0000000000104e05 Attempt 2 Apr 13 2019, 20:31 为什么WA? 因为混淆了dfs中visit的顺序与stack,无法保证stack中会装满曾经visit过的点。 而Competitive Submissions的Attempt 1 使用的回溯算法至少是对的

二叉树的前/中/后序遍历，都可视为特殊的dfs,这三者互相之间的区别，只在于print的时机不同。那为什么没有用visit数组控制？这是树的特性决定的。

牛客：矩阵中的路径。

在什么情况下使用visit控制？为了避免沿环路前进（会造成重复和死循环）。为什么有时候退出某结点时又将它的visit重新置为false? 因为此路径不被接受，再沿新路径遍历时，此点又可以被访问了。
事实上，使用visit并不是dfs的特点，在图上使用bfs一样需要使用visit。