当前位置 博文首页 > Keven_11的博客:广度优先搜索BFS bfs
广度优先搜索,又称宽度优先搜索,简称 bfs,我们以后都会用 bfs 来表示广度优先搜索。与深度优先搜索不同的是,广度优先搜索会先将与起始点距离较近的点搜索完毕,再继续搜索较远的点,而深搜却是沿着一个分支搜到最后。
bfs 从起点开始,优先搜索离起点最近的点,然后由这个最近的点扩展其他稍近的点,这样一层一层的扩展,就像水波扩散一样。
bfs 需要借助队列来实现:
最后写出来的代码框架如下:
void bfs(起始点) {
将起始点放入队列中;
标记起点访问;
while (如果队列不为空) {
访问队列中队首元素x;
删除队首元素;
for (x 所有相邻点) {
if (该点未被访问过且合法) {
将该点加入队列末尾;
}
}
}
队列为空,广搜结束;
}
cs