概述
- DFS：深度优先遍历，从一条路径走到叶节点，然后回溯，继续遍历（不撞南墙不回头）
- BFS：广度优先遍历，从根节点，一层一层的遍历，每一层把所有的节点都遍历完成。
递归思想
- 递归在于不断调用自己的函数，层层深入，直到遇到递归终止条件后层层回溯，其思想与dfs的思想不谋而合；因此，可以使用递归来实现dfs。
- 递归的进入比较容易理解，但是递归的回溯是在计算机底层执行的，我们无法看到。因此这是理解递归的唯一一个难点。
让我们来看一下这样一个简单的递归程序
DFS解决全排列问题
- 对于全排列问题，n = 3 为例，进行DFS搜索：
步骤1：
假设有 3 个空位，从前往后填数字，每次填一个位置，填的数字不能和前面一样。
最开始的时候，三个空位都是空的：__ __ __
首先填写第一个空位，第一个空位可以填 1，填写后为：1 __ __
填好第一个空位，填第二个空位，第二个空位可以填 2，填写后为：1 2 __
填好第二个空位，填第三个空位，第三个空位可以填 3，填写后为： 1 2 3这时候，空位填完，无法继续填数，所以这是一种方案，输出。
步骤2：
然后往后退一步，退到了状态：1 2 __ 。剩余第三个空位没有填数。第三个空位上除了填过的 3 ，没有其他数字可以填。
因此再往后退一步，退到了状态：1 __ __。第二个空位上除了填过的 2，还可以填 3。第二个空位上填写 3，填写后为：1 3 __
填好第二个空位，填第三个空位，第三个空位可以填 2，填写后为： 1 3 2
这时候，空位填完，无法继续填数，所以这是一种方案，输出。
步骤3：
然后往后退一步，退到了状态：1 3 __ 。剩余第三个空位没有填数。第三个空位上除了填过的 2，没有其他数字可以填。
因此再往后退一步，退到了状态：1 __ __。第二个空位上除了填过的 2，3，没有其他数字可以填。
因此再往后退一步，退到了状态：__ __ __。第一个空位上除了填过的 1，还可以填 2。第一个空位上填写 2，填写后为：2 __ __
填好第一个空位，填第二个空位，第二个空位可以填 1，填写后为：2 1 __
填好第二个空位，填第三个空位，第三个空位可以填 3，填写后为：2 1 3这时候，空位填完，无法继续填数，所以这是一种方案，输出。
步骤4：
然后往后退一步，退到了状态：2 1 __ 。剩余第三个空位没有填数。第三个空位上除了填过的 3，没有其他数字可以填。
因此再往后退一步，退到了状态：2 __ __。第二个空位上除了填过的 1，还可以填 3。第二个空位上填写 3，填写后为：2 3 __
填好第二个空位，填第三个空位，第三个空位可以填 1，填写后为：2 3 1这时候，空位填完，无法继续填数，所以这是一种方案，输出。
步骤5：
然后往后退一步，退到了状态：2 3 __ 。剩余第三个空位没有填数。第三个空位上除了填过的 1，没有其他数字可以填。
因此再往后退一步，退到了状态：2 __ __。第二个空位上除了填过的 1，3，没有其他数字可以填。
因此再往后退一步，退到了状态：__ __ __。第一个空位上除了填过的 1，2，还可以填 3。第一个空位上填写 3，填写后为：3 __ __
填好第一个空位，填第二个空位，第二个空位可以填 1，填写后为：3 1 __
填好第二个空位，填第三个空位，第三个空位可以填 2，填写后为：3 1 2这时候，空位填完，无法继续填数，所以这是一种方案，输出。
步骤6：
然后往后退一步，退到了状态：3 1 __ 。剩余第三个空位没有填数。第三个空位上除了填过的 2，没有其他数字可以填。
因此再往后退一步，退到了状态：3 __ __。第二个空位上除了填过的 1，还可以填 2。第二个空位上填写 2，填写后为：3 2 __
填好第二个空位，填第三个空位，第三个空位可以填 1，填写后为：3 2 1
这时候，空位填完，无法继续填数，所以这是一种方案，输出。
步骤7：
然后往后退一步，退到了状态：3 2 __ 。剩余第三个空位没有填数。第三个空位上除了填过的 1，2，没有其他数字可以填。
因此再往后退一步，退到了状态：3 __ __。第二个空位上除了填过的 1，2，没有其他数字可以填。
因此再往后退一步，退到了状态：__ __ __。第一个空位上除了填过的 1，2，3，没有其他数字可以填。
此时深度优先搜索结束，输出了所有的方案。
算法
- 用
path[]数组保存排列，当排列的长度为 n 时，是一种方案，输出。 - 用
state[]数组表示数字是否用过。当state[i]为 1 时：i已经被用过，state[i]为0时，i没有被用过。 dfs(i)表示的含义是：在path[i]处填写数字，然后递归的在下一个位置填写数字。- 回溯：第
i个位置填写某个数字的所有情况都遍历后， 第i个位置填写下一个数字。(对于for循环的回溯)
题目
代码
#include <iostream>
using namespace std;
const int N = 10;
int n;
int path[N]; //保存序列
bool state[N]; //表示状态位，没被占用为false,否则为true
void dfs(int u )
{
if (u == n) //遍历到叶节点，就打印
{
for (int i = 0; i < n; i ++)
{
cout << path[i] << " ";
}
cout << endl;
}
for (int i = 1; i <= n; i ++) //从1开始
{
if (!state[i]) //如果数字 i 没有被用过
{
path[u] = i; //放入空位
state[i] = 1; //数字被用，修改状态
dfs(u + 1); //填下一个位
state[i] = 0; //回溯，取出 i(这里是回溯到for循环)
}
}
}
int main()
{
cin >> n;
dfs(0); //从0开始，意味着第一个数字的下标为0，也可以从1开始，看个人习惯
return 0;
}
