这一周主要解决了广度优先搜索（BFS）、深度优先搜索（DFS)的基本思想和在具体题目中的应用，以及几道STL的例题。
广度优先搜索：
个人理解：
广度优先搜索是从第一个结点开始，入队，按照定义的规则，拓展下一层可能出现的所有结点，将所有可能出现的结点依次入队，然后将队首元素出队，然后依次将现存队首所有可能拓展的结点入队，拓展完毕后，将队首元素出队，以此类推，直到找到了目标或队列为空没找到。广度优先搜索对于搜索最短路径具有优势，并且其搜索到的路径一定的最短的，因为它是判断完这一层的所有结点后，再去判断下一层，因此搜索到的结果一定是最短的，广度优先搜索符合队列先进先出的特点。
举一个经典的例子：迷宫问题
有一个迷宫，有障碍物和边界，剩余的是空地，需要求从起点到终点的最短路径长度。（行和列小于等于50，输入几行几列，定义迷宫情况，输入起点坐标和终点坐标，输出最短步长）
首先， 我们定义探索的规则，我们定义按照顺时针的方向来探索，即右→下→左→上的方向来探索，算法步骤大体分为两步：一是将起点入队，二是将队首结点可拓展的所有结点入队，然后将队首结点出队。重复该步骤，直到到达目标或队列为空。
首先我们定义起点位置，它的步数为0，然后 它可以扩展的点为右边和下边，依次将两个点入队，步数变为1，然后将队首出队：
然后依次将队首（第一行第二列）可拓展的点入队，完成后队首出队，再将现任队首可拓展的结点入队，队首出队，按照右→下→左→上的规则，这一层新拓展的结点步数变为2（遇到障碍物和边界不能通行）：
判断是否到达目标点，没有的话继续将这一层能拓展的下一层结点依次入队，并将这一层的结点都出队：
判断是否到达终点，没有则继续拓展下一层可能出现的结点，这一层的结点出队：
这里可能是粗箭头的情况也可能是细箭头的情况，取决于哪个元素在前，先拓展哪个元素，需要注意的是，拓展完的元素要被标记，后续路径不可再用，继续下一层拓展：
这一层拓展发现到达了终点，搜索终止，输出步长即为最短的路径步数。
下面来看实现这一过程的代码：
#include<bits/stdc++.h>
using namespace std;
int a[100][100], v[100][100] ={0}; //v[100][100]为访问数组，判断该位置是否可以通过 0可访问 1不可访问
int startx, starty, p, q;
struct point{
int x;
int y;
int step;
};
queue<point> r; //申请队列
int dx[4] = {0, 1, 0,-1 }; //定义方向数组
int dy[4] = {1, 0, -1, 0}; //来实现右下左上的规则
// 输入 1 代表可以通过 2代表不能通过
/*
5 3
1 1 1
1 2 1
1 1 1
2 1 1
1 1 1
1 1 4 3
*/
int main(){
int n, m;
cin >> n >> m; //输入n行m列
//定义迷宫情况
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
cin >> a[i][j];
}
}
cin >> startx >> starty >> p >> q; //起点坐标和终点坐标
//算法部分
point start; //因为起点是一个结构体类型 所以这个要为起点的输入定义一个结构体
//并进行初始化
start.x = startx;
start.y = starty;
start.step = 0;
//将起点入队
r.push(start);
//然后将起点的状态设置为已经访问
v[startx][starty] = 1;
int flag = 0; //没有到达终点的话
while(!r.empty())
{
//取出队首元素 来拓展
int x = r.front().x;
int y = r.front().y;
//先判断如果队首已经到达终点
if(x ==p && y == q)
{
flag = 1;
cout << r.front().step;
break;
}
//如果没有到达终点 进行四个方向的试探
for(int k = 0; k < 4; k++)
{
int tx = x + dx[k];
int ty = y + dy[k];//a[tx][ty]表示拓展的点
if(a[tx][ty] == 1 && v[tx][ty] == 0) //如果探索的点是空地并且未被访问
{
//将它入队
//再申请一个临时的结构体类型 来将每一次满足条件的探索的点入队
point temp;
temp.x = tx;
temp.y = ty;
temp.step = r.front().step+1; //新入队的点的步数一定是现在处于队首的点的步数+1
r.push(temp);
v[tx][ty] = 1; //入队的点要被设置为已访问
}
}
//当四个方向都已经访问完了 需要将队首元素出队
r.pop();
}
if(flag == 0)
{
cout <<"No answer!" << endl; //表示没有找到答案
}
return 0;
}
深度优先先搜索：
个人理解：
深度优先搜索是从第一个结点开始，一头摸到黑，直到碰到终点或遇到死胡同返回上一层结点再从上一层的结点的下一条路开始继续一头到黑，每次到达终点都记录经过的步长，最后来不断更新最小步长，也就是遍历所有的路之后来寻找最小步长。
举一个简单的例子便于理解，依旧是上一个的迷宫问题：
还是n行m列格子（n和m都<=50）每个空格要么是空地要么是障碍物，求起点到终点的最短步长，按照右→下→左→上的规则进行试探：
第一趟，按照右→下→左→上的规则进行试探完毕后就是这样的结果，这次步长是5，但是否是最短步长现在还不确定，得走完所有的才能确定，每走完一步都要标记已访问（用星星表示），到达终点后就进行回溯，返回上一层结点，返回之前要把现在的结点标记未访问，继续在上一层结点处探索新的路径：
大体就是按照这样一个思路来探寻每一种情况，来看代码：
#include<bits/stdc++.h>
using namespace std;
int n, m, startx, starty, p, q, mins = 10001;
int a[100][100];//1表示空地 2表示障碍物
int v[100][100] = {0}; //0表示未访问 1表示已访问
int dx[4] = {0, 1, 0, -1}; //方向数组
int dy[4] = {1, 0, -1, 0}; //分别表示右下左上情况坐标的偏移量
/* 输入样例
5 3
1 1 1
1 2 1
1 1 1
2 1 1
1 1 1
1 1 4 3
*/
void dfs(int x, int y, int step)
{
if(x == p && y == q)
{
if(step < mins)
{
mins = step;
}
//当不是更小的路径或是更新完最短路径后要进行回溯
return ;
}
//算法部分 进行右下左上的试探
for(int k = 0; k < 4; k++)
{
int tx = x + dx[k];
int ty = y + dy[k]; //下一个试探位置的坐标
if(a[tx][ty] == 1 && v[tx][ty] == 0)
{
v[tx][ty] = 1; // 将它设置为已经访问 并从它进行深度优先搜索
dfs(tx, ty, step+1);
v[tx][ty] = 0;//退回去后要将它设置为未访问
}
}
}
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
cin >> a[i][j];
}
}
cin >> startx >> starty >> p >> q;
//从起点开始深度优先搜索要将起点设置为已访问
v[startx][starty] = 1;
dfs(startx, starty, 0);
//深度优先搜索完后最小步数也就出来了 所以输出就行
cout << mins;
}
总结一下，两种搜索的解题思路：
BFS：
将队首结点可拓展的点入队，拓展完毕或没有可拓展的点后将队首结点出队，重复该步骤，直到找到目标或队列为空。BFS搜索的路径一定是最短的。BFS用到了队列。
DFS：
从某点出发，沿一个方向一头走到黑，当找到目标就回溯，以找到所有的路径，来确定最短路径，效率没有BFS高。DFS的另一种方式用到了栈。
对于一般的题目，广度搜索已然足够。
最后的心得体会：
最近做的几道STL的题，就是感觉无论题目定义的是怎样的一种情景，最后代码实现都是用数字来堆叠，看的例题的过程中，前两次看完全不知道是怎么实现的过程，后来自己运行了一下，输入数据后打印出来才明白它是怎样去实现的，给我的感触是看不懂的代码，多看几次，没有学到的知识点就立刻去查，并结合自己运行代码实践来更好的理解代码。还有就是，遇到想不通这一步或下一步该从哪走的时候，正所谓好记性不如烂笔头，可以在纸上写写，顺着代码的思路过程一步一步往下走，那些脑子里模糊不清的路口也会变得逐渐清晰，还有对于自己不会的点，一定不要自己闷头硬做，要善于向别人请教，问别人问题，甚至两个人互相交流想法，相互指正，这样也可以更好地一起进步。