深度优先搜索是图的一种搜索方式，以深度为优先级去进行搜索，通俗地说就是"不撞南墙不回头"，对于当前正在搜索的路径而言，只有把当前路径给搜索完了，即走到无路可走时，才回返回进而搜索另一条路。
假设我们有一个二叉树，共有10个节点，以下是DFS的简单示范：
从根节点开始向下搜索
然后搜索到2号节点
继续不断向深层处的节点搜索，搜索到4号节点
最后搜索到7号节点
当搜索到7号节点后，我们发现无路可走了，因为7号节点是当前这条路径下最深处的节点，因此，我们需要进行回溯操作
当回溯到4号节点时，我们发现4号节点并没有另一条路，也就是说从4号节点向下搜索的话，只能搜索到7号节点，但是可是刚刚才从7号节点回溯上来诶，我们总不可能又搜索到7号，然后又回溯到4号无限下去吧…所以，我们得再次回溯，也就是跳到2号节点上。
当再次跳到2号节点上时，我们发现从2号节点开始，还有另一条路可以走。那我们就走下去！
此时又有两条路可以走，我们先去往8号
走到8号，我们发现又走到头了，那就再对它使用回溯吧！！！
这次我们选择另一条路，走到9号
然后我们发现又双走到头了，因此，再次回溯，从9号跳到5号，再跳到2号，然后再跳到1号(因为5号，2号向下的路我们已经走过了，但我们发现1号节点向下的路还有一条是我们没走过滴)
接下来搜索类似，我们走到3号，然后走到6号，然后走到10号
当10号走完后，这颗树的每个节点都被搜索过了，最后回溯到根节点
值得一提的是，深搜作为一种算法来说，并没有像二分等这些算法有固定的模板，我更愿意把它当作一种思想。如何实现DFS呢，我们通常用栈(递归来实现)。我们做题时通常会写一个dfs函数，然后在dfs函数内部，又会不断调用dfs函数，通常像下面看到的这样：
以下是自我总结的模版
void dfs(int step){ if(到达目的地) 输出 return; for(int i = 1;i<=方案数;i++) { if(方案可行) { 保存路径; dfs(step+1); 回溯 } } }
例题1
题解
#include<iostream> using namespace std; int n; int ans[1000010];//记录值 bool st[1000010];//记录是否用过这个数值 void dfs(int step)//当前所走的步数 { if (step == n + 1)//当前所走的步数为总步数加一 则说明已经走完了 { for (int i = 1; i <= n; i++) { cout << ans[i] << " ";//输出走的每一步的值； } cout << endl; return; } //如果走的这一步没有到总步数加一 for (int i = 1; i <= n; i++) //从1号位开始搜 { if (st[i] == false)//如果i这个数没有被查到过 { ans[step] = i;//将i的值赋值给第step步数 st[i] = true;//标记 i 这个值已经被用过; dfs(step + 1);//向 step的下一步走; st[i] = false; } } return; } using namespace std; int main() { cin >> n; dfs(1); return 0; }
例题2
题解
#include<iostream> using namespace std; int n, r; int ans[1000010]; bool st[1000010]; void dfs(int num, int step)//num代表当前数字的值 step代表当前的步数 { if (step == r + 1)//当前所走的步数为总步数加一 则说明已经走完了 { for (int i = 1; i <= r; i++) { cout << ans[i] << " "; //输出走的每一步的值； } cout << endl; return; } //如果走的这一步没有到总步数加一 for (int i = num + 1; i <= n; i++) // 从 i 号位开始搜 { if (st[i] == false) //如果i这个数没有被查到过 { ans[step] = i; //将i的值赋值给ans[step] st[i] = true; //标记 dfs(i, step + 1); //搜索下一步 st[i] = false; //清除标记 ans[step] = 0; //抹除值 } } return; } int main() { cin >> n >> r; dfs(0, 1); return 0; }
