你钥匙丢了，你要找；饭卡丢了，你要找；卷子丢了，就不要了你要找。等等等等。 当你找钥匙时，你会想最近去过什么地方，然后一个一个再回去一趟。 然后再看那个地方有什么，哪里最有可能放钥匙。 再接着，你从可能性最大的地方开始找，按照可能性排序，比如，柜子或枕头下面
深度优先搜索顾名思义，一条路走到黑，撞了南墙才回头。搜索与回溯是计算机中常用的算法，很多问题无法根据某种确定的计算法则来求解。
这时，可以利用搜索与回溯来求解。
我们可以先选择一种可能的情况向前探索，并一直沿着探索。一旦发现原来的选择是错误的，就退回退一步重新选择，继续向前探索，如此反复进行，直到得到答案或无解。
如走迷宫，进入迷宫后，先随意选择一个方向，一步一步向前走，直到碰到一个死胡同及前方无路可走。这时，先看看其他方向是否有路走，若有，则沿着这条路直着走下去；反则若已经无路可走，则退到上一个路口，再看看其他方向有没有路；接下来就像之前一样，不断走，碰壁，退回。直到找到出口或发现无出口为止。 看上面这个图，从1开始先找2，然后再找4，再找8,。当H不为我们要找的答案时，就退一步，再找9，如此；查找顺序是A–B--D–H--I–E--J–C--F–G.一条道走到黑有木有。
它由一个根节点出发，遍历所有的子节点，进而把图中所有的可以构成树的集合都搜索一遍，达到全局搜索的目的。
一般的，当搜索深度较小、问题递归方式比较明显时，用递归方法设计好，它可以使得程序结构更简捷易懂。
虽然很多问题都可以用dfs来遍历每一种情况，从而得出最优解，但由于时间复杂度太高，暴力搜索，容易超时。
题目描述 一矩形阵列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。如阵列:
0234500067 1034560500 2045600671 0000000089
有4个细胞。
输入格式：整数0<=m,n<=100(m行，n列) M行n列0到9的数字（中间没有空格） 输出格式：细胞的个数。 样例数据 input： 4 10 0234500067 1034560500 2045600671 0000000089 output： 4
#include<bits/stdc++.h> using namespace std; char a[1010][1010]; int n,m,ans,x,y; int dx[5]={-1,0,1,0}; int dy[5]={0,1,0,-1};//定义方向 void dfs(int x,int y) { for(int i=0;i<=3;i++) { int xx=x+dx[i]; int yy=y+dy[i]; if(a[xx][yy]!='0') { a[xx][yy]='0'; dfs(xx,yy); } } } int main () { // freopen("input.in","r",stdin); // freopen("output.out","w",stdout); cin>>n>>m; memset(a,'0',sizeof(a)); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { cin>>a[i][j]; } } for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(a[i][j]!='0') { ans++; a[i][j]='0'; dfs(i,j); } } } cout<<ans; return 0; }广度优先搜索（宽度优先搜索），说，它是最简便的图的搜索算法之一，也是很多重要的图的算法的原型害，难死我了。 Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽搜类似的思想。
从初始节点开始，应用算符生成第一层节点，检查目标节点是否在这些后继节点中，若没有，再用产生式规则将所有第一层的节点逐一扩展，得到第二层节点，并逐一检查第二层节点中是否包含目标节点。若没有，再用算符逐一扩展第二层的所有节点…，如此反复，直到找到目标。
我个人觉得它就是换了个搜索方式。dfs是一条路走到黑，bfs…我不是很会形容 明明是语文不好 比喻一下吧，你眼镜掉了，然后你蹲下来摸，先摸近的地方，没有再摸远的。
我们看图吧。 它就是从1开始，先找2,3，然后再找4,5，接着找6,7； 比如dfs是挖井，bfs是修路，一个竖着来，一个横着干。挖井很累啊！所以超时了。修路面积大啊，所以空间溢出了。
这里推荐大家先弄明白 队列 dfs和bfs的程序实现的区别在于：dfs用的递归，bfs用的队列辅助。
广度优先搜索法一般无回溯操作，对于解决最短或最少问题特别有效，而且寻找深度小，所以运行速度比深度优先搜索算法法要快些。
一般需要存储产生的所有结点，占的存储空间要比深度优先大得多，因此程序设计中，必须考虑溢出和节省内存空间得问题。（需要开大量的数组单元用来存储状态）。
【问题描述】 小晨的电脑上安装了一个机器翻译软件，他经常用这个软件来翻译英语文章。
这个翻译软件的原理很简单，它只是从头到尾，依次将每个英文单词用对应的中文含义来替换。对于每个英文单词，软件会先在内存中查找这个单词的中文含义，如果内存中有，软件就会用它进行翻译；如果内存中没有，软件就会在外存中的词典内查找，查出单词的中文含义然后翻译，并将这个单词和译义放入内存，以备后续的查找和翻译。
假设内存中有 MM 个单元，每单元能存放一个单词和译义。每当软件将一个新单词存入内存前，如果当前内存中已存入的单词数不超过 M−1M−1，软件会将新单词存入一个未使用的内存单元；若内存中已存入 MM 个单词，软件会清空最早进入内存的那个单词，腾出单元来，存放新单词。
假设一篇英语文章的长度为 NN 个单词。给定这篇待译文章，翻译软件需要去外存查找多少次词典？假设在翻译开始前，内存中没有任何单词。
【输入】 输入文件名为 translate.in，输入文件共 22 行。每行中两个数之间用一个空格隔开。
第一行为两个正整数 MM 和 NN，代表内存容量和文章的长度。
第二行为 NN 个非负整数，按照文章的顺序，每个数（大小不超过 10001000）代表一个英文单词。文章中两个单词是同一个单词，当且仅当它们对应的非负整数相同。
【输出】 输出文件 translate.out 共 11 行，包含一个整数，为软件需要查词典的次数。
【样例 1】 ex_translate1.in 3 7 1 2 1 5 4 4 1 ex_translate1.out 5 样例说明 整个查字典过程如下：每行表示一个单词的翻译，冒号前为本次翻译后的内存状况：
空：内存初始状态为空；
11：查找单词 11 并调入内存； 1 21 2：查找单词 22 并调入内存； 1 21 2：在内存中找到单词 11； 1 2 51 2 5：查找单词 55 并调入内存； 2 5 42 5 4：查找单词 44 并调入内存替代单词 11； 2 5 42 5 4：在内存中找到单词 44； 5 4 15 4 1：查找单词 11 并调入内存替代单词 22。 共计查了 55 次词典。
【样例 2】 ex_translate2.in 2 10 8 824 11 78 11 78 11 78 8 264 ex_translate2.out 6 【数据范围】 对于 10%10% 的数据有 M=1M=1，N≤5N≤5；
对于 100%100% 的数据有 0<M≤1000<M≤100，0<N≤10000<N≤1000。
时间限制：1s1s 空间限制：128MB
#include<bits/stdc++.h> using namespace std; int n,m,ans,a[10101]; bool f[1010]; int q[1010],head=-1,tail=0; void work() { memset(f,false,sizeof(f)); memset(q,0,sizeof(q)); for(int i=1;i<=m;i++) { if(!f[a[i]]) { if(tail-head+1==n) f[q[head++]]=false; q[++tail]=a[i]; f[a[i]]=true; ans++; } } } int main () { // freopen("translate.in","r",stdin); // freopen("translate.out","w",stdout); cin>>n>>m; for(int i=1;i<=m;i++) cin>>a[i]; work(); cout<<ans; return 0; }不管是BFS还是DFS，它们虽然好用，但由于时间和空间的局限性，以至于它们只能解决数据量小的问题。
总之，一般情况下，深度优先搜索法占内存少但速度较慢，广度优先搜索算法占内存多但速度较快，在距离和深度成正比的情况下能较快地求出最优解。因此在选择用哪种算法时，要综合考虑。决定取舍。
