DFS-深度优先搜索（Depth First Search）—1
深度优先搜索算法，作为最常用的算法之一，在很多地方都有它的身影，也被很多人称为“万能的搜索”，可能这个说话有点过了，但是由此也可以看出它有多么强大。好了，多说无益，我们一起来看看这个“万能的算法”的真面目：
先从一道题目说起：假设现在有0~9一共10个数字，每个数字只能并且一定要出现一次，求它们的全排列。
全排列，举个例子：数字1、2、3的全排列有：123、132、213、231、312、321 一共6种。如果不知道深度优先搜索算法，看到这道题可能第一反应可能是使用枚举，那么得使用10重循环，并且还要判断10个数字是不是有重复的，我想除非你是个代码狂魔，不然的话你肯定不会去写这个代码。那么有更好的办法吗？of course，这就是典型的深度优先搜索算法（以下简称dfs）题。 在每次选取数字的时候，我们都有10种可能，当然不是每一种可能都能成功，因为我们不能选取重复的数字，那么怎么办呢，我们这里可以采用标记数组的思想，定义一个数组标记0~9一共10个数字的状态（是否被选取），如果当前数字已经被选取那么筛选下一个数字，否则的话就选择当前的数字，下一步仍然采取这种筛选方法（很明显是个递归的思想），那么我们脑子里就可以架构出大概的代码结构：
for(int i = 0; i < 10; i++)
{
if(book[i] == 0) // 假设标记数组值为0代表这个数字没有选过
{
book[i] == 1; // 这个数字被选了，标记
筛选下一步的数字
}
}那么我们的选择什么时候结束呢？当然是我们的数字都被选完了的时候，由此我们需要加一个变量来记录我们选择的数字个数。由此我们可以架构出大致的代码：
void dfs(int step)
{
/*
* 当筛选完最后一个数字时返回,
*（注意不是9，因为第9位数字是最后一个数字，但是此时还没筛选完第9位数字）
*/
if(step == 10)
{
输出且返回
}
for(int i = 0; i < 10; i++) //否则继续循环筛选
{
if(book[i] == 0)
{
book[i] = 1;
dfs(step + 1); // 筛选的步数加一
}
}
}这样的话我们把大致的代码思想已经架构出来了，但是现在还有一个问题：上面代码的book标记数组只有将数字标记为已经被选择状态的部分（book[i] = 1;），但是当我们下一次要筛选的时候这个数字不是用不了了吗？如果你也想到了这个问题，那么恭喜你，你已经理解了这道题的思路，在每一轮筛选结束之后，我们在确实要将选中的数字取消标记，这样才能进行下一轮的筛选（注意是下一轮而不是下一步）。那么，我们再加上数字取消标记的代码：
void dfs(int step)
{
/*
* 当筛选完最后一个数字时返回,
*（注意不是9，因为第9位数字是最后一个数字，但是此时还没筛选完第9位数字）
*/
if(step == 10)
{
输出且返回
}
for(int i = 0; i < 10; i++) //否则继续循环筛选
{
if(book[i] == 0)
{
book[i] = 1; // 标记数字已经被使用
dfs(step + 1);
book[i] = 0; // 结束这一轮的筛选之后，对用过的数字取消标记用于下一轮筛选
}
}
}题目要求我们输出啊，那么数字的储存和结果的输出在哪里进行呢，到了这一步这些都不难了，下面给出完整的代码：
#include <iostream>
using namespace std;
const int n = 10; // 一共10个数字
int a[n]; // 储存数字用的数组
int count; // 符合条件的结果总数
int book[10]; // 标记数组，初值全为0
void dfs(int step)
{
if(step == n) // 如果筛选完最后一个数字
{
count++; // 结果数加一
for(int i = 0; i < n; i++) // 输出这个符合条件的排列
{
cout << a[i];
}
cout << endl;
return ; // 这句返回语句最好有，不然会增加程序执行所耗费的时间
}
for(int i = 0; i < n; i++)
{
if(book[i] == 0)
{
book[i] = 1; // 标记数字已经被使用过
a[step] = i; // 储存数字
dfs(step + 1); // 筛选下一步
book[i] = 0; // 对使用过的数字取消标记，供下一轮筛选使用
}
}
}
int main()
{
dfs(0); // 从第0步开始筛选
cout << count << endl; // 输出结果总数
}Ok了，这就是深度优先搜索最基本的模型：
/*
* 深度优先搜索：每一次利用递归将当前情况搜索到最深处（一条道走到黑，不撞南墙不回头），然后利用循环枚举出所有当前可能的情况
* 递归：做好当前怎么做，下一步怎么做和当前是一样的情况
*
* 模型：void dfs(int step)
* {
* 判断边界，是否返回
* for(int i = 0; i < n; i++) 尝试每一种可能（有些并不会成功）
* {
* 尝试成功则继续下一步递归：dfs(step + 1);
* }
* 返回
* }
*/运行结果：
好了，大功告成。 如果对过程仍然不是很清楚可以把1、2、3一共3个数字带入代码走一遍过程就行了。如果有不正确之处还请指正。 谢谢观看。。。