广度优先遍历 (BFS)
类似树的层次遍历，首先访问起始顶点v,然后选取与v邻接的全部顶点w1,w2,…wn，进行访问。再依次访问与w1,w2,…wn邻接的全部顶点。依次类推，直到所有顶点都被访问过为止。从顶点一层层向外拓展和遍历，实现是需要用到队列。
深度优先遍历（DFS)
首先访问出发节点v,将其标记为已访问过；然后选取与v邻接的未被访问的任意一个顶点w，并访问它；再选取与w邻接的未被访问的任意一个顶点并访问，依次重复进行。当一个顶点的所有邻接顶点都被访问过，则依次退回到最近被被访问过的顶点，如果该顶点还有其他邻接顶点未被访问，则从这些未被访问的顶点中取一个重复上述访问过程。
BFS算法模板
image.png
DFS 算法模板
思想：一直往深处走，直到找到解或者走不下去为止
image.png
来到题目加深下理解
Description
定义一个二维数组：
int maze[5][5] = {
0, 1, 0, 0, 0,
0, 1, 0, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};
它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。
Input
一个5 × 5的二维数组，表示一个迷宫。数据保证有唯一解。
Output
左上角到右下角的最短路径，格式如样例所示。
Sample Input
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
Sample Output
(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)
题目原地址
以及ac代码 这是我以前ac的代码，那时候采用的是数组模拟队列的形式，因为要采用dfs回溯整体路径，使用路径是需要保留的。
整体思路就是先采用bfs找出最短的路线，然后采用dfs去回溯整条过来的路线
#include<iostream>
#include<string.h>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stdio.h>
using namespace std;
#define xi
int s[6][6];//题目说是5*5的二维数组，用户标记用
int X[]={1,0,-1,0};//定义bfs是需要遍历的4个方向
int Y[]={0,1,0,-1};
struct xs
{
int x,y;//当前的坐标位置
int i;//队列中的那一个位置
int f;//记录上一步的位置，也就是xy从数组中的那一个位置过来的
}g[100861];
void dfs(int a)
{
if(a==0) //整条路回溯用，a==0，表示到了最开始的位置，这时候终止
{
printf("(%d, %d)\n",0,0);
return ;
}
dfs(g[a].f);//上一个脚步的位置
printf("(%d, %d)\n",g[a].x,g[a].y);
}
void bfs()
{
xs l;
l.x=0;l.y=0;l.i=0;l.f=0;
g[0]=l;
int aa=0;int bb=1;
while(aa<bb)
{
//为什么要采用数组模拟队列，就是因为拿出元素后不能删除元素，因为要回溯用
l=g[aa];//拿出需要遍历的元素，从0开始
aa++;//准备下一个元素
if(l.x==4&&l.y==4) {//判断是否到了右下角，如果到了，就进行dfs回溯
aa--;
//cout<<g[aa].x<<g[aa].y;
dfs(aa);
return ;
}
for(int a=0;a<4;a++)
{
xs ll=l;//遍历4个方向的位置
ll.x+=X[a];
ll.y+=Y[a];
if(ll.x>=0&&ll.y>=0&&ll.x<=4&&ll.y<=4&&s[ll.x][ll.y]==0)//是否越界判断加是否被标记过
{
s[ll.x][ll.y]=1;
ll.i=bb;队列中的位置
ll.f=l.i;//从哪里来的，用于回溯用
g[bb]=ll;加入队列
bb++;
}
}
}
}
int main()
{
#ifdef xin
freopen("1.txt","r",stdin);
#endif
for(int a=0;a<5;a++)
for(int b=0;b<5;b++)
cin>>s[a][b];
bfs();
return 0;
}
