浅谈深度优先搜索
一、问题引入
输入一个数n，输出1~n的全排列。
分析：我们可以先将问题形象化，假如有编号为1、2、3的3张扑克牌和编号为1、2、3的3个盒子，现在需要将这3张扑克牌分别放到3个盒子里面，并且每个盒子有且只能放一张扑克牌。那么一共有多少种不同的做法呢？
不难看出，一共会出现6种排列，分别是：123、132、213、231、312、321。
二、解决问题的步骤
1，现在我们来解决最基本的问题：如何往小盒子中放扑克牌。每一个小盒子都可能放1号、2号或者3号扑克牌，这需要一一尝试，在这里我们只需要一个for循环即可搞定：
for(i=1;i<=n;i++)
{
a[step]=i; //将i号扑克牌放入到第step个盒子中
}在这里数组a是用来表示小盒子的，变量step表示当前正处在第step个小盒子面前。a[step]=i；就是将第i号扑克牌放入到第step个盒子中。这里有一个问题那就是，如果一张扑克牌已经放到别的盒子中了，那么此时就不能再放入同样的扑克牌到当前的小盒子中，因为此时手中已经没有这张扑克牌了。因此需要一个数组book来标记哪些牌已经使用了：
for(i=1;i<=n;i++)
{
if(book[i] == 0) //book[i]等于0表示i号扑克牌仍然在手上
{
a[step]=i; //将i号扑克牌放入到第step个盒子中
book[i]=1; //将book[i]设为1，表示i号扑克牌已经不在手上了
}
}2，,接下来我们继续处理step+1个小盒子。那么如何处理step+1个盒子呢？这将是我们接下来要解决的问题
（1）首先我们把刚才处理第step个小盒子的代码封装成一个函数
void dfs(int step) //step表示现在站在第几个盒子面前
{
for(i=1;i<=n;i++)
{
//判断扑克牌i是否还在手上
if(book[i] == 0) //book[i]等于0表示i号扑克牌仍然在手上
{
a[step]=i; //将i号扑克牌放入到第step个盒子中
book[i]=1; //将book[i]设为1，表示i号扑克牌已经不在手上了
}
}
}（2）接下来的事情就很好办了。在处理完第step个小盒子之后，紧接着处理第step+1个小盒子，处理第step+1的小盒子的方法就是dfs(step+1)
void dfs(int step) //step表示现在站在第几个盒子面前
{
for(i=1;i<=n;i++)
{
//判断扑克牌i是否还在手上
if(book[i] == 0) //book[i]等于0表示i号扑克牌仍然在手上
{
a[step]=i; //将i号扑克牌放入到第step个盒子中
book[i]=1; //将book[i]设为1，表示i号扑克牌已经不在手上了
dfs(step+1); //这里通过函数的递归调用来实现（自己调用自己）
book[i]=0; //将刚才的扑克牌收回，才能进行下一次尝试（这一步很关键）
}
}
}上面代码中的book[i]=0十分重要，这句话的作用是将小盒子中的扑克牌收回，因为在一次摆放尝试结束返回的时候，如果不把刚才放入小盒子中的扑克牌收回，那将无法再进行下一次摆放。
（3）最后一个待解决的问题：什么时候该输出一个满足要求的序列？
其实当我们处理到第n+1个小盒子的时候（即step=n+1），那么说明前n个盒子都已经放好扑克牌了，这里就将1~n个小盒子中的扑克牌编号打印出来即可。
注意：打印完毕一定要立即return，不然这个程序就会永无止尽地运行下去，想一想为什么？
三、完整代码
#include<stdio.h>
int a[10],book[10],n; //C语言的全局变量在没有赋值以前默认为0，因此这里的book数组无需全部再次赋初始值0
void dfs(int step) //step表示现在站在第几个盒子面前
{
int i;
if(step == n+1)
{
//输出一种排列（1~n号盒子中的扑克牌编号)
for(i=1;i<=n;i++)
printf("%d",a[i]);
printf("\n");
return; //返回之前的一步（最近调用dfs函数的地方）
}
//此时站在第step个盒子面前，应该放哪张牌呢
//按照1、2、3...n的顺序一一尝试
for(i=1;i<=n;i++)
{
//判断扑克牌i是否还在手上
if(book[i] == 0) //book[i]等于0表示i号扑克牌仍然在手上
{
a[step]=i; //将i号扑克牌放入到第step个盒子中
book[i]=1; //将book[i]设为1，表示i号扑克牌已经不在手上了
dfs(step+1); //这里通过函数的递归调用来实现（自己调用自己）
book[i]=0; //将刚才的扑克牌收回，才能进行下一次尝试（这一步很关键）
}
}
return;
}
int main()
{
scanf("%d",&n); //输入的时候要注意n为1~9整数
dfs(1); //首先站在1号小盒子面前
getchar();getchar();
return 0;
} 
刚才例子的代码虽然不超过20行，却饱含深度优先搜索（Depth First Search,DFS）的基本模型。
理解深度优先搜索的关键在于解决“当下该如何做”（==下一步该怎么做）。
下面的代码就是深度优先搜索的基本模型：
void dfs(int step)
{
//判断边界
for(i=1;i<=n;i++) //尝试每一种可能
{
dfs(step+1) //继续下一步
}
return; //返回
}每一种尝试都是一次“扩展”。
每次站在一个盒子面前的时候，其实都有n种扩展方法，但是并不是每种扩展都能够成功。
四、再举个例子
【】【】【】+【】【】【】=【】【】【】，将数字1~9分别填入9个【】中，每个数字智能使用一次使得等式成立。
http://www.cnblogs.com/OctoptusLian/p/6675885.html
分析：这就相当于你手中有编号为1~9的九张扑克牌，然后将这九张扑克牌放到九个盒子中，并使得以上等式成立。
转述——> 判断 a【1】*100+a【2】*10+a【3】+a【4】*100+a【5】*10+a【6】== a【7】*100+a【8】*10+a【9】 这个等式是否成立。
#include<stdio.h>
int a[10],book[10],total=0;
void dfs(int step) //step表示现在站在第几个盒子面前
{
int i;
if(step==10)
{
if(a[1]*100+a[2]*10+a[3]+a[4]*100+a[5]*10+a[6]==a[7]*100+a[8]*10+a[9])
{
/*如果满足要求，可行解+1，并打印这个解*/
total++;
printf("%d%d%d+%d%d%d=%d%d%d\n",a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8],a[9]);
}
return; //返回之前的一步（最近调用的地方）
}
/*站在第step个盒子面前，按照1、2、3...n的顺序一一尝试*/
for(i=1;i<=9;i++)
{
if(book[i]==0)
{
a[step]=i;
book[i]=1;
dfs(step+1);
book[i]=0;
}
}
return;
}
int main()
{
dfs(1);
printf("total=%d",total/2);
return 0;
}五、感受
深度优先搜索，在我的理解看来就是有一种不撞南墙不回头的倔强性格，一定要“碰壁”，才肯回头。
感触颇深的是那道等式题，第一次看到想着是九个for循环遍历一遍，很累，而且容易出错，而dfs无疑减轻了这样的运算负担。