前置知识
注意 该算法的前置知识为队列（queue）,如果没有学习，请点击这里进行学习
BFS的介绍
BFS（宽度优先搜索 Breadth-First Search）是一种用于图的遍历或搜索的算法。它从一个节点开始，逐层遍历图中的所有节点。BFS通常用队列来实现，因为它需要按照节点的发现顺序来访问它们。
工作原理
BFS的工作原理可以总结为以下几个步骤
- 循环：只要队列不为空，就执行以下操作：
- 出队一个节点（我们称之为当前节点）。
- 访问当前节点的所有未访问的邻居节点（子节点）。
- 将每个未访问的邻居节点（子节点）标记为已访问，并将其入队。
BFS算法的特点
- 层级遍历：它按层级顺序访问节点，这意味着它会先访问所有与源节点相邻的节点，然后是那些节点的邻居，以此类推。
- 最短路径：在无权图中，BFS可以找到从源节点到其他任何节点的最短路径。
- 时间复杂度：对于有V个顶点和E条边的图，BFS的时间复杂度是O(V+E)。
- 空间复杂度：在最坏的情况下，BFS可能需要O(V)的空间来存储所有节点的访问状态。
图示演示
下面进行进行图示演示：
首先1为根节点
假如我们使用的是DFS，那么DFS序如下
如果我们使用BFS，那么可以理解为按照深度对图进行分层，例如下图，分为1-4共4层，每次遍历先遍历完上一层的所有节点，接着再遍历下一层，首先根节点1入队,遍历完1之后，1的所有子节点入队，1做一次标记并且退队
然后接着对队列中的元素2、3、4、5进行遍历，遍历完2后将2的子节点入队并且对2做标记且让2出队，后续接着遍历完3、4、5，各自子节点入队后各自再做一次标记并退队
接着遍历队列中的元素，直到最后一个元素退队后没有新的元素入队，即队列为空，遍历结束
例题：马的遍历
依然是DFS中出现的这道Luogu例题： https://www.luogu.com.cn/problem/P1443 我们接下来用BFS的方法解答一下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| #include<bits/stdc++.h>
using namespace std;
int num[401][401];
struct node{
int x,y;
};
queue<node>q;
int move_x[8] = {1,1,2,2,-1,-1,-2,-2};
int move_y[8] = {2,-2,1,-1,2,-2,1,-1};
int main(){
int n,m,begin_x,begin_y;
cin>>n>>m>>begin_x>>begin_y;
memset(num,-1,sizeof(num));
num[begin_x][begin_y] = 0;
node tmp = {begin_x,begin_y};
q.push(tmp);
......
}
|
接下来开始BFS，代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| while(!q.empty())
{
node now = q.front();
q.pop();
int now_x = now.x;int now_y = now.y;
for(int i = 0; i < 8; i++)
{
int next_x = now_x + move_x[i];
int next_y = now_y + move_y[i];
if(next_x < 1 || next_y < 1 || next_x > n || next_y > m || num[next_x][next_y] != -1) continue;
num[next_x][next_y] = num[now_x][now_y] + 1;
node t = {next_x,next_y};
q.push(t);
}
}
|
然后我们就完成了对所有情况的遍历，接着对答案进行输出
1
2
3
4
5
| for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++) cout<<num[i][j]<<" ";
cout<<endl;
}
|
然后我们就完成了这道题目。全部代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| #include<bits/stdc++.h>
using namespace std;
int num[401][401];
struct node{
int x,y;
};
queue<node>q;
int move_x[8] = {1,1,2,2,-1,-1,-2,-2};
int move_y[8] = {2,-2,1,-1,2,-2,1,-1};
int main(){
int n,m,begin_x,begin_y;
cin>>n>>m>>begin_x>>begin_y;
memset(num,-1,sizeof(num));
num[begin_x][begin_y] = 0;
node tmp = {begin_x,begin_y};
q.push(tmp);
while(!q.empty())
{
node now = q.front();
q.pop();
int now_x = now.x;int now_y = now.y;
for(int i = 0; i < 8; i++)
{
int next_x = now_x + move_x[i];
int next_y = now_y + move_y[i];
if(next_x < 1 || next_y < 1 || next_x > n || next_y > m || num[next_x][next_y] != -1) continue;
num[next_x][next_y] = num[now_x][now_y] + 1;
node t = {next_x,next_y};
q.push(t);
}
}
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++) cout<<num[i][j]<<" ";
cout<<endl;
}
return 0;
}
|
