BFS、DFS算法原理及代码模板（附模板题）

78 阅读 0 评论 52 点赞

我是靠谱客的博主超级金针菇，最近开发中收集的这篇文章主要介绍BFS、DFS算法原理及代码模板（附模板题），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

前言

BFS、DFS这两个搜索算法都是对图的遍历，从图中某点出发，按照某种方法对图的所有顶点进行访问，每个点仅访问一次。

因为图对于树而言相对复杂，其中的任意顶点都可能与其他顶点相邻，所以在图的遍历中必须记录已经被访问过的点。

根据搜索路径的不同，我们可以将遍历图的方法分为两种：广度优先搜索和深度优先搜索。
实现bfs和dfs都需要解决的一个问题就是如何存储图。一般有两种方法：邻接矩阵和邻接表。这里为简单起
见，均采用邻接矩阵存储，说白了也就是二维数组。

实例

我的眼镜掉在了以我为中心边长为5的一块矩阵，现在我要找我的眼镜，假设每次都可以搜索前后左右的任意一个方向，我每次下手找都可以搜索目标方向边长为1的面积，下面我用DFS、和BFS两种方法找我的眼镜…

DFS算法

思想：一直往深处走，知道找到解或者走不下去为止

因为我每次找眼镜都会按前后左右来判断时候符合需要搜索的条件，所以当我没有找到眼镜，并且下次要找的点没有超过边界时，会一直向前搜索，到头发现没有找到眼镜，返回一步后，因为前这个方向我已经找过了，我有了后左右，当然我不会傻到找我找过的地方，只剩了左右两个方向，判断左，符合条件，找左方向，进入那个点后，又有前后左右四个方向，继续判断…直到找到眼镜或者所有地方都走过了~~~~

DFS（int x, int y） //这里假设存的是二维数组，x、y表示两个坐标
{
if (找到解)
{
}
for (......)
//每到一个点下一步都有上下左右四个方向可以走，这里用一个循环遍历方向数组表示四个方向
{
// 如果这个点(a,b)符合要求并且没走过
flag[a][b] = 1; //标记‘1’表示走过
DFS(a, b);
//进入下一次递归
flag[a][b] = 0; //回溯，标记‘0’表示可以走
}
}
}

关于回溯 flag[a][b] = 0; //回溯
假如DFS每次都是按上下左右这个顺序判断是否能走，上走过了，每次都走下这个方向，最后发现走到了死胡同，而每次都标记了走过的坐标，就会导致无法退回去访问进入其他的点
而我们把“ flag[a][b] = 0; //回溯”放在了进入递归的下边，当走入了死胡同往回退的时候，每次出来都把上个点取消标记，仔细想一下，死胡同的这个点因为标记过不会再次进入了

框架

bool vst[maxn][maxn];
// 访问标记
int map[maxn][maxn];
// 坐标范围
int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0}; // 方向向量，(x,y)周围的四个方向
bool CheckEdge(int x, int y) // 边界条件和约束条件的判断
{
if (!vst[x][y] && ...) // 满足条件
return 1;
else // 与约束条件冲突
return 0;
}
void dfs(int x, int y)
{
vst[x][y] = 1;
// 标记该节点被访问过
if (map[x][y] == G) // 出现目标态G
{
...... // 做相应处理
return;
}
for (int i = 0; i < 4; i++)
{
if (CheckEdge(x + dir[i][0], y + dir[i][1])) // 按照规则生成下一个节点
dfs(x + dir[i][0], y + dir[i][1]);
}
return; // 没有下层搜索节点，回溯
}
int main()
{
...... return 0;
}

模板题1
模板题2

BFS算法

思想：广度优先搜索类似于树的层次遍历过程。它需要借助一个队列来实现。

不了解队列的同学可以看一下我写的这篇博客 STL模板库

我的眼镜又掉到了地上，怎么办呢，找呗~
依然是上面那种情况，这次我会把前后左右四个方向的点一次判断，如果符合要找的条件（没有找过，没有超界）就把它放进一个队列当中，下面开始循环，访问队列中的队首元素，对其上下左右四个点一次访问，判断时候符合需要找的条件，如果符合，把符合的这几个点放进队列的后面，对队首的四个方向判断完后就把它出队，当然我还需要标记一下我找过的地方，毕竟年纪大了记性比较差，下面我又访问队列中的队首，判断完后把符合条件的点加到队列中，再把这个队首出队…直到队列访问完了，找遍了所有的点或者是我找到了我的眼镜…结束

BFS()
{
queue<int> q;//初始化队列Q 
while(!q.empty())
//队列不为空
{
if() //判断是否找到了目标
{
}
//队首出队
for()
{
//依旧是四个方向
//符合条件的入队
//标记入队的点
}
}
}

框架

bool vst[maxn][maxn]; // 访问标记
int dir[4][2]={0,1,0,-1,1,0,-1,0}; // 方向向量
struct State // BFS 队列中的状态数据结构
{
int x,y; // 坐标位置
int Step_Counter; // 搜索步数统计器
};
bool CheckState(State s) // 约束条件检验
{
if(!vst[s.x][s.y] && ...) // 满足条件
return 1;
else // 约束条件冲突
return 0;
}
void bfs(State st)
{
queue<State> q;
// BFS 队列
State now, next;
// 定义2 个状态，当前和下一个
st.Step_Counter = 0; // 计数器清零
q.push(st);
// 入队
vst[st.x][st.y] = 1; // 访问标记
while (!q.empty())
{
now = q.front(); // 取队首元素进行扩展
if (now == G)
// 出现目标态，此时为Step_Counter 的最小值，可以退出即可
{
...... // 做相关处理
return;
}
for (int i = 0; i < 4; i++)
{
next.x = now.x + dir[i][0]; // 按照规则生成下一个状态
next.y = now.y + dir[i][1];
next.Step_Counter = now.Step_Counter + 1; // 计数器加1
if (CheckState(next))
// 如果状态满足约束条件则入队
{
q.push(next);
vst[next.x][next.y] = 1; //访问标记
}
}
q.pop(); // 队首元素出队
}
return;
}
int main()
{
...... return 0;
}