深度优先搜索：

搜索分为两类：深度优先搜索(DFS)和广度优先搜索(BFS)，来看看深度优先搜索。 深度优先搜索(DFS)可以说就是“一条路走到黑”的一种搜索方法，有序的尝试每一种可能，在进行每一种可能尝试时，都将这种可能性贯彻到底，一直到该种可能被尝试到出了确切的结果或者走到了边界。深度优先搜索就是“一条路走到黑”或者“不撞南墙不回头”的搜索算法。

例子：

输入一个数n（n是不超过9的自然数），对1~n的数进行全排列后输出，每个数不能相同。这题能直接用循环解，进行枚举遍历，若数不相同就输出，现在用深度优先搜索遍历，先上代码：

#include<stdio.h> int a[10], book[10], n; void dfs(int step) { int i; if(step == n + 1) //输出条件 { for(i = 1; i <= n; i++) { printf("%d", a[i]); } printf("\n"); return; } for(i = 1; i <= n; i++) { if(book[i] == 0) { a[step] = i; book[i] = 1; dfs(step + 1); book[i] = 0; } } return; } int main() { scanf("%d", &n); dfs(1); return 0; }

对代码进行解释：

1.首先我们定义一个长度为10的数组a来储存数字，再定义一个标记数组book来标记哪些数出现过。 2.深度优先搜索代码使用递归来实现，因为每一步的处理都一样。 3.首先用一个for循环来判断哪些数没有出现过，再将这个数放入数组a的对应位置中，用book来标记此数已经出现过，递归进行下一步。 4.将刚才出现过的数重新置0，代表这个数又可以用了，再return返回上一次尝试，此时手中多了一个数，可以开始新的尝试了。

参考书：《啊哈算法》