浅谈bfs广度优先搜索在数字漫水填充flood-fill算法中的应用
浅谈bfs广度优先搜索在数字漫水填充flood-fill算法中的应用
BFS，其英文全称是Breadth First Search。 BFS并不使用经验法则算法。从算法的观点，所有因为展开节点而得到的子节点都会被加进一个先进先出的队列中。一般的实验里，其邻居节点尚未被检验过的节点会被放置在一个被称为 open 的容器中（例如队列或是链表），而被检验过的节点则被放置在被称为 closed 的容器中。（open-closed表）
讨论方向
在一个二维数组中，任意设置一个点为起始点，值为1，并将其相邻摩尔邻居(Moore Neighborhood)的值（浅绿色）设置为比中心值（黄色）多1，并忽略已填充过的值。
这时候，将一张10*10的表格填充出来
1
2
3
4
5
6
7
8
9
10
10 10 10 10 10 10 10 10 10 10
10 9 9 9 9 9 9 9 9 9
10 9 8 8 8 8 8 8 8 8
10 9 8 7 7 7 7 7 7 7
10 9 8 7 6 6 6 6 6 6
10 9 8 7 6 5 5 5 5 5
10 9 8 7 6 5 4 4 4 4
10 9 8 7 6 5 4 3 3 3
10 9 8 7 6 5 4 3 2 2
10 9 8 7 6 5 4 3 2 1
当然，我们还需要考虑障碍物的情况
1
2
3
4
5
6
7
8
9
10
10 10 10 10 10 10 10 10 10 -1
10 9 9 -1 9 -1 9 9 9 9
-1 9 8 8 8 8 8 8 8 8
10 9 8 7 7 7 7 7 7 7
10 9 8 7 6 6 6 6 6 6
-1 9 8 7 6 5 5 5 5 5
-1 9 8 -1 6 5 4 4 4 -1
10 9 8 7 -1 5 4 3 3 3
-1 9 8 7 6 5 4 3 2 2
10 9 8 7 6 5 4 3 2 1
障碍物不应该被覆盖、填充，并应该避免将障碍物作为摩尔邻居的中心（因为-1+1永远是0）
实现方法
这种填充的实现方法有很多，其中一种实现方法就是使用广度优先搜索算法(Breadth First Search, BFS)。从第一段对于BFS的简介中我们得知，其工作原理本质就是循环将未检测的节点加入到队列中。队列，遵循先进先出原则(First In First Out, FIFO)。
▲ （图片来源于dev.to)
在这里，我们不讨论队列这种数据结构是如何实现的。C++中，我们可以在文件头部添加#include <queue> 来调用现成的队列数据结构。
大体思路为：
- 首先将起始点（根节点）放入队列中。
- 当队列不为空
- 取出队列中的第1个x，y坐标，并将其从队列中移除
- 将这个x，y坐标对应的点作为摩尔邻居的中心点
- 如果其相邻摩尔邻居合法（不出界，不为-1，未被填充过）
- 将这个x，y坐标对应的数值更改为，这个摩尔邻居中心的数值+1
- 将这个x，y坐标添加进队列中
- 返回步骤2
▲ 动画演示（时长约3-4分钟）
具体代码(C++)
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
138
139
140
141
142
143
144
145
146
147
148
149
#include <queue>
...
...
// 检查坐标是否合法
bool validCoord(int indexX, int indexY, int gridWidth, int gridHeight) {
if (indexX < 0 || indexY < 0) {
return false;
}
if (indexX >= gridWidth || indexY >= gridHeight) {
return false;
}
return true;
}
void bfs(int** grid, int gridWidth, int gridHeight, int cIndexX, int cIndexY) {
grid[cIndexY][cIndexX] = 1;
// Create two new queue to store x and y coordinate
// 新建两个队列存储x轴和y轴的值
std::queue<int> queueX;
std::queue<int> queueY;
// 将起始点x轴的值添加到queueX队列中
queueX.push(cIndexX);
// 将起始点y轴的值添加到queueY队列中
queueY.push(cIndexY);
// 当这两个队列中都不为空时（当然它们应该同时变空，不然就有问题）
while (!queueX.empty() && !queueY.empty()) {
// 获取到queueX队列中第一个x轴的值
cIndexX = queueX.front();
// 将这个值从queueX队列中删除
queueX.pop();
// 获取到queueY队列中第一个y轴的值
cIndexY = queueY.front();
// 将这个值从queueY队列中删除
queueY.pop();
// 获取到摩尔中心坐标对应的值
int centerEleValue = grid[cIndexY][cIndexX];
// 相邻的摩尔邻居有8中可能性，N,S,W,E,NW,NE,SW,SE
// NW
// 当前摩尔邻居的坐标
int nIndexX = cIndexX - 1;
int nIndexY = cIndexY - 1;
// 检查坐标是否合法，不合法则直接跳过
if (validCoord(nIndexX, nIndexY, gridWidth, gridHeight)) {
// 检查坐标中的值是否为0，不是0说明被填充过或是障碍物-1
if (grid[nIndexY][nIndexX] == 0) {
// 设置该坐标的值为摩尔中心值+1
grid[nIndexY][nIndexX] = centerEleValue + 1;
// 把这两个坐标添加到对应的队列中
queueX.push(nIndexX);
queueY.push(nIndexY);
}
}
// W
nIndexX = cIndexX - 1;
nIndexY = cIndexY;
if (validCoord(nIndexX, nIndexY, gridWidth, gridHeight)) {
if (grid[nIndexY][nIndexX] == 0) {
// set the value +1 to the center element
grid[nIndexY][nIndexX] = centerEleValue + 1;
// then push into queue
queueX.push(nIndexX);
queueY.push(nIndexY);
}
}
// SW
nIndexX = cIndexX - 1;
nIndexY = cIndexY + 1;
if (validCoord(nIndexX, nIndexY, gridWidth, gridHeight)) {
if (grid[nIndexY][nIndexX] == 0) {
// set the value +1 to the center element
grid[nIndexY][nIndexX] = centerEleValue + 1;
// then push into queue
queueX.push(nIndexX);
queueY.push(nIndexY);
}
}
// N
nIndexX = cIndexX;
nIndexY = cIndexY - 1;
if (validCoord(nIndexX, nIndexY, gridWidth, gridHeight)) {
if (grid[nIndexY][nIndexX] == 0) {
// set the value +1 to the center element
grid[nIndexY][nIndexX] = centerEleValue + 1;
// then push into queue
queueX.push(nIndexX);
queueY.push(nIndexY);
}
}
// S
nIndexX = cIndexX;
nIndexY = cIndexY + 1;
if (validCoord(nIndexX, nIndexY, gridWidth, gridHeight)) {
if (grid[nIndexY][nIndexX] == 0) {
// set the value +1 to the center element
grid[nIndexY][nIndexX] = centerEleValue + 1;
// then push into queue
queueX.push(nIndexX);
queueY.push(nIndexY);
}
}
// NE
nIndexX = cIndexX + 1;
nIndexY = cIndexY - 1;
if (validCoord(nIndexX, nIndexY, gridWidth, gridHeight)) {
if (grid[nIndexY][nIndexX] == 0) {
// set the value +1 to the center element
grid[nIndexY][nIndexX] = centerEleValue + 1;
// then push into queue
queueX.push(nIndexX);
queueY.push(nIndexY);
}
}
// E
nIndexX = cIndexX + 1;
nIndexY = cIndexY;
if (validCoord(nIndexX, nIndexY, gridWidth, gridHeight)) {
if (grid[nIndexY][nIndexX] == 0) {
// set the value +1 to the center element
grid[nIndexY][nIndexX] = centerEleValue + 1;
// then push into queue
queueX.push(nIndexX);
queueY.push(nIndexY);
}
}
// SE
nIndexX = cIndexX + 1;
nIndexY = cIndexY + 1;
if (validCoord(nIndexX, nIndexY, gridWidth, gridHeight)) {
if (grid[nIndexY][nIndexX] == 0) {
// set the value +1 to the center element
grid[nIndexY][nIndexX] = centerEleValue + 1;
// then push into queue
queueX.push(nIndexX);
queueY.push(nIndexY);
}
}
}
}
显然，这种方法看起来有一些繁琐。其实这8次我们可以用两个for循环代替，如下
具体如何循环相邻的摩尔邻居，请参考这篇文章
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
#include <queue>
...
...
// 检查坐标是否合法
bool validCoord(int indexX, int indexY, int gridWidth, int gridHeight) {
if (indexX < 0 || indexY < 0) {
return false;
}
if (indexX >= gridWidth || indexY >= gridHeight) {
return false;
}
return true;
}
void bfs(int** grid, int gridWidth, int gridHeight, int cIndexX, int cIndexY) {
grid[cIndexY][cIndexX] = 1;
// Create two new queue to store x and y coordinate
// 新建两个队列存储x轴和y轴的值
std::queue<int> queueX;
std::queue<int> queueY;
// 将起始点x轴的值添加到queueX队列中
queueX.push(cIndexX);
// 将起始点y轴的值添加到queueY队列中
queueY.push(cIndexY);
// 当这两个队列中都不为空时（当然它们应该同时变空，不然就有问题）
while (!queueX.empty() && !queueY.empty()) {
// 获取到queueX队列中第一个x轴的值
cIndexX = queueX.front();
// 将这个值从queueX队列中删除
queueX.pop();
// 获取到queueY队列中第一个y轴的值
cIndexY = queueY.front();
// 将这个值从queueY队列中删除
queueY.pop();
// 获取到这个x，y坐标对应的值
int centerEleValue = grid[cIndexY][cIndexX];
// nIndexY, nIndexY is neighborhood index of cIndexX, cIndexY
// Find right corner of moore neighborhood
int nIndexX = cIndexX - 1;
int nIndexY = cIndexY - 1;
// Use for loop iterate the moore neighborhood
for (int y = nIndexY; y < nIndexY + 3; ++y) {
for (int x = nIndexX; x < nIndexX + 3; ++x) {
// Check if it is the center point
if (y == cIndexY && x == cIndexX) {
continue;
}
// Check if the index is valid
if (validCoord(x, y, gridWidth, gridHeight)) {
// if the grid is unexplored
if (grid[y][x] == 0) {
// set the value +1 to the center element
grid[y][x] = centerEleValue + 1;
// then push into queue
queueX.push(x);
queueY.push(y);
}
}
}
}
}
}
本文由作者按照 CC BY 4.0 进行授权