深度优先搜索是搜索算法的一种。以数据结构中树的深度遍历为例，其沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所有边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。属于盲目搜索。
观察上诉百度的定义，发现有两个特性，一个是选择源节点，二是从源节点尽可能深的遍历，抽象出来可以把深度优先搜索这两个特性描述为岔道口（描述选择）和死胡同（描述尽可能深）。
所以当我们发现一个问题即对每一个结点有选择又有一定的规模、终点时，可以考虑深度优先算法，而深度优先算法的关键也在把握分支选择岔道口和结束条件死胡同。看到结束条件这里，会突然发现，这一点和递归很像，实际上使用递归可以更好的实现深度优先搜索。
下面是一些实战
1. 组合+素数判断
题目：
已知 n 个整数b1,b2,…,bn
以及一个整数 k（k＜n）。
从 n 个整数中任选 k 个整数相加，可分别得到一系列的和。
例如当 n=4，k＝3，4 个整数分别为 3，7，12，19 时，可得全部的组合与它们的和为： 3＋7＋12=22 3＋7＋19＝29 7＋12＋19＝38 3＋12＋19＝34。
现在，要求你计算出和为素数共有多少种。
例如上例，只有一种的和为素数：3＋7＋19＝29。
分析：这个问题分两个阶段，一个是任选求和，一个是判断素数，判断素数容易解决，关键在与前者；可以考虑，这n个数从第一个开始，可以选他也可以不选他，选了他就求和，当选的数到达k个对和再判断。
于是代码如下：
#include<iostream> #include<cmath> using namespace std; int n,k,count=0,a[22],b[22]={false}; bool ifsushu(int x){ int m=sqrt(x); if(x<4) return true; for(int i=2;i<=m;i++){ if(x%i==0) return false;} return true; } void dfs(int index,int sum,int pos){ if(index==k+1) //已经选了n个数，死胡同 { if(ifsushu(sum)) count++; return; } for(int i=pos;i<=n;i++) //从前向后选，pos让不重复选 { if(!b[i]){ sum+=a[i]; b[i]=true; dfs(index+1,sum,pos+1); //选他 sum-=a[i]; //回溯 b[i]=false; } } } int main(){ scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) scanf("%d",&a[i]); dfs(1,0,1); printf("%d\n",count); return 0; }
当然上述代码在codeup里面会编译超时，实际上在选择过程中全局变量sum的回溯和递归和的传递会浪费时间，如果对程序优化，用一个数组p来记录选择的数，最后选好n个数后在判断是不是复数也行；此外，还有一点，上面的程序属于盲目搜索，如果选到第n-k位都没有选择一个元素，说明后面的也不用选了，选不齐k位，这个时候，约束条件i<=n可以改成i+k-index<=n。
经过上面两步改进后下程序符合题意：
#include<iostream> #include<cmath> using namespace std; int sum,n,k,count=0,a[22],p[22]; bool ifsushu(int x){ int m=sqrt(x); if(x<4) return true; for(int i=2;i<=m;i++){ if(x%i==0) return false;} return true; } void dfs(int index,int pos){ if(index==k+1) //已经选了n个数，死胡同 { sum=0; for(int i=1;i<=k;i++) sum+=p[i]; if(ifsushu(sum)) count++; return; } for(int i=pos;i+index-k<=n;i++) //从前向后选，pos让不重复选，判断条件是确保选的数能够 k个 { p[index]=a[i]; //选他 dfs(index+1,pos+1); } } int main(){ scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) scanf("%d",&a[i]); dfs(1,1); printf("%d\n",count); return 0; }
进过上述例子其实还发现我们没有必要将全局变量sum用在递归的参数中，以后设计可以注意。
2.出栈序列
题目:
栈是常用的一种数据结构，有n令元素在栈顶端一侧等待进栈，栈顶端另一侧是出栈序列。你已经知道栈的操作有两•种：push和pop，前者是将一个元素进栈，后者是将栈顶元素弹出。现在要使用这两种操作，由一个操作序列可以得到一系列的输出序列。请你编程求出对于给定的n，计算并输出由操作数序列1，2，…，n，经过一系列操作可能得到的输出序列总数。
分析：用一个过程采模拟进出栈的过程，可以通过循环加递归来实现回溯：重复这样的过程，如果可以进栈则进一个元素，如果可以出栈则出一个元素。就这样一个一个地试探下去，当出栈元素个数达到n时就计数一次(这也是递归调用结束的条件)。
#include<iostream> using namespace std; int count, n; void dfs(int push, int pop) { if(pop==n)//出栈次数都为n，则是一个序列 { count++; return; } if(push<n) //选择进栈 dfs(push+1, pop); if(pop<n && pop < push)//选择出栈 dfs(push, pop+1); } int main() { scanf("%d",&n); dfs(0,0); printf("%d\n", count); return 0; }
