BFS与DFS
一、BFS
1.BFS模板
（1）介绍
BFS 是 “广度优先搜索”（Breadth-First Search）的缩写，是一种用于图形和树结构遍历的算法。BFS 从一个起始节点开始，首先访问所有与该节点距离为1的节点，然后访问距离为2的节点，依此类推，直到访问所有节点或者找到目标节点。具体步骤如下
初始化：
- 创建一个队列，用于存储待访问的节点
- 将起始节点放入队列中，并标记为已访问
遍历过程：
- 从队列的前端取出一个节点，称为当前节点
- 访问当前节点的所有邻接节点（即与当前节点直接相连的节点）
- 对于每个邻接节点，如果它未被访问过，将其放入队列，并标记为已访问
重复：
广度优先搜索的特征为从起点开始，由近及远（树结构，只管的解释就是一层一层的搜索，队列中最多同时存在2层以内的元素节点）进行广泛的搜索。因此，目标顶点离起点越近，搜索结束得就越快
（2）BFS与DFS对比
BFS与DFS的区别：
bfs 遍历节点是先进先出（使用的工具为队列），dfs遍历节点是先进后出（使用栈）
bfs 是按层次访问的，dfs 是按照一个路径一直访问到底，当前节点没有未访问的邻居节点时，然后回溯到上一个节点，不断的尝试，直到访问到目标节点或所有节点都已访问
bfs 适用于求源点与目标节点距离最近的情况，例如：求最短路径。dfs 更适合于求解一个任意符合方案中的一个或者遍历所有情况，例如：全排列、拓扑排序、求到达某一点的任意一条路径
（3）BFS模板
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
|
const int N = num;
vector<Node> adj[N+1];
vector<int> visited[N+1];
vector<Node> q;
int BFS(Node start, Node target)
{
入队(初始状态);
visited[初始状态] = true;
while(!空队)
{
Node front = 出队()
for(Node node: adj[front])
{
if (visited[node] == true)
continue;
if (node == target)
{
输出答案;
return 0;
}
v[node] = true;
}
}
return -1;
}
|
如下图，对其进行 BFS 遍历，若先遍历左子树，则顺序是FBGADICEH，由此知，对于树，BFS的遍历方式就是层序遍历
（4）八数码问题
视频教程：跳转
题目
1
2
3
4
| 在3×3的棋盘上摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格，空格用0来表示。空格周围上下左右相邻的棋子可以移到空格中。
现给出原始状态和目标状态，求实现从初始布局到目标布局的最少步骤（初始状态的步数为0）
答案：5
|
样例输入输出
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| 【输出格式】
输出移动所用最少的步数。
【样例1输入】
2 8 3
1 6 4
7 0 5
1 2 3
8 0 4
7 6 5
【样例1输出】
5
【样例2输入】
2 8 3
1 6 4
7 0 5
0 1 2
3 4 5
8 7 6
【样例2输出】
17
|
如下图可以将该图抽象为BFS问题如下，每个节点有四种移动方式，就是0可以上下左右进行移动，当然需要判断移动是否合法
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
| #include <bits/stdc++.h>
using namespace std;
typedef struct node{
int m[3][3],parent = -1;
}M;
int equal(M a, M b){
for(int i = 0; i < 3; i++)
for(int j = 0; j < 3; j++)
if(a.m[i][j] != b.m[i][j])
return 0;
return 1;
}
void printM(M a){
for(int i = 0; i < 3; i++){
for(int j = 0; j < 3; j++)
cout << a.m[i][j];
cout << endl;
}
cout << endl;
}
vector <M> OPEN,CLOSE;
int ifFindAnswer = 0,cnt;
int opt[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
int main() {
M *s0, *sg, front;
int x, y;
s0 = (struct node *) malloc(sizeof(struct node));
sg = (struct node *) malloc(sizeof(struct node));
cout << "请输入初始状态：（请用0代替空格）" << endl;
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
cin >> s0->m[i][j];
cout << "请输入目标状态：（请用0代替空格）" << endl;
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
cin >> sg->m[i][j];
OPEN.push_back(*s0);
while (OPEN.size() != cnt)
{
front = OPEN[cnt];
if (equal(front, *sg) == 1)
{
ifFindAnswer = 1;
break;
}
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 3; j++)
{
if (front.m[i][j] == 0)
{
x = i;
y = j;
break;
}
}
}
for (int i = 0; i < 4; i++)
{
int flag = 1;
if (x + opt[i][0] > -1 && x + opt[i][0] < 3 && y + opt[i][1] > -1 && y + opt[i][1] < 3)
{
M temp = front;
swap(temp.m[x][y], temp.m[x + opt[i][0]][y + opt[i][1]]);
for (int j = 0; j < CLOSE.size(); j++)
{
if (equal(CLOSE[j], temp) == 1)
{
flag = 0;
break;
}
}
for (int i = x + 1; i < OPEN.size(); i++)
{
if (equal(OPEN[i], temp) == 1)
{
flag = 0;
break;
}
}
if (flag == 1)
{
temp.parent = cnt;
OPEN.push_back(temp);
}
}
else
continue;
}
CLOSE.push_back(OPEN[cnt++]);
}
if (ifFindAnswer == 0)
{
cout << "找不到路径!!";
}
else
{
cout << "找到路径，路径是：" << endl;
stack <M> ans;
ans.push(OPEN[cnt]);
while (ans.top().parent != 0)
{
ans.push(OPEN[ans.top().parent]);
}
ans.push(OPEN[0]);
while (ans.size() != 0)
{
printM(ans.top());
ans.pop();
}
}
}
|
二、BFS与DFS
视频教程：跳转
一般搜索算法的流程框架
1.定义点集 X 为已经处理的点（去重），点集 F 为已发现但尚未处理的点（BFS队列，DFS栈）
2.初始化点集 X 为空，点集 F 只包含搜索的起点
3.只要点集 F 不为空，循环4-6
- 4.从点集 F 中取出一点 v
- 5.处理点v，将点 v 加入点集 X
- 6.遍历 v 的出边，对于每个 v 的邻居，若既不在点集 X 中也不在点集 F 中，则加入点集 F
7.搜索结束，点集 X 里的点搜索过的点
1.递归DFS
递归DFS，不需要认为的创建栈，而是使用系统栈
流程框架如下：
1.定义点集 X 为已经处理的点（去重）
2.初始化点集 X 为空
3.递归搜索点 v (开始时搜索起点)
- 4.处理点 v ，将点 v 加入点集 X
- 5.遍历 v 的出边，对于每个 v 的邻居，若不在点集 X 中，则递归处理该点
6.搜索结束，点集X里的点都为搜索过的点
使用栈的DFS与递归DFS的区别：
下图左边为使用栈的DFS，右图为使用递归的DFS
三、BFS的基础理论
1.BFS的基础理论
视频教程：跳转
特点：
从根节点开始，一圈一圈，一层一层向外遍历
从近到远，由内而外
如何实现：
使用队列
- 源点入队
- 源点出队，距离为1的子节点入队
- 距离为1的点出队，距离源点距离为2的点入队（距离为1的节点的子节点）
（1）基本代码实现
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 N;
bool v[N+1];
vector<int> adj[N+1];
queue<int> q;
void bfs(int s)
{
q.push(s);
v[s] = true;
while (!q.empty())
{
int cur = q.front();
q.pop();
for(auto next: adj[cur])
{
if(v[next]) continue;
q.push(next);
v[next] = true;
}
}
}
|
（2）棋盘图扩展方式（重点）
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
39
40
41
42
43
44
45
| #include <bits/stdc++.h>
using namespace std;
int N;
bool v[N+1][N+1];
queue<pair<int, int>> q;
void bfs(int sx, int sy)
{
q.push({sx, sy});
v[sx][sy] = true;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
while(!q.empty())
{
auto[curx, cury] = q.front();
q.pop();
for(int i = 0;i<4;i++)
{
int nx = curx + dx[i];
int ny = cury + dy[i];
if(0<nx && nx<=N && 0<ny && ny <= N)
{
if(v[nx][ny])
continue;
q.push({ny,ny});
v[nx][ny] = true;
}
}
}
}
|
（3）BFS能做但DFS不能做
无权图的最短路径
（4）岛屿数量
问题描述：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| 给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例1 ：
输入：grid1 = [
[“1”,“1”,“1”,“1”,“0”],
[“1”,“1”,“0”,“1”,“0”],
[“1”,“1”,“0”,“0”,“0”],
[“0”,“0”,“0”,“0”,“0”]
]
输出：1
---------------
示例2 ：
输入：grid2 = [
[“1”,“1”,“0”,“0”,“0”],
[“1”,“1”,“0”,“0”,“0”],
[“0”,“0”,“1”,“0”,“0”],
[“0”,“0”,“0”,“1”,“1”]
]
输出：3
|
代码实现：
核心思路：使用棋盘扩展方式的 BFS 将一个区域山下左右连续的1全部变为0，一个棋盘可以这样使用几次 BFS 就表示有几座岛屿
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
| #include <bits/stdc++.h>
using namespace std;
class Solution
{
private:
queue<pair<int, int>> q;
int cnt= 0;
int n, m;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
public:
void bfs(int i, int j, vector<vector<char>> &grid)
{
q.push({i, j});
grid[i][j] = '0';
while(!q.empty())
{
auto p = q.front();
q.pop();
for(int i=0;i<4;i++)
{
int nx = p.first + dx[i];
int ny = p.second + dy[i];
if(0<=nx && nx<n && ny<=0 && ny<m)
{
if(grid[nx][ny] == '1')
{
grid[nx][ny] = '0';
q.push({nx, ny});
}
}
}
}
}
};
int numIslands(vector<vector<char>> &grid)
{
n = grid.size();
m = grid[0].size();
for(int i = 0;i<n;i++)
{
for(int j = 0;j<m;j++)
{
if(grad[i][j] == '1')
{
bfs(i, j, grid);
cnt++;
}
}
}
return cnt;
}
|
