广度优先搜索

什么广度优先搜索(BFS)

和树(Tree)的数据结构一样,我们也可以访问图(Graph)的所有节点。

广度优先搜索(breadth-first search,BFS)是搜索图的算法之一。

图遍历可以用来寻找特定的顶点或寻找两个顶点之间的路径,检查图是否连通,检查图是否含有环,等等。

广度优先搜索会指定一个顶点,从这个顶点开始遍历图结构,遍历时先访问这个顶点的相邻顶点,然后再按队列的顺序访问相邻顶点的下一层顶点,直到到达要搜索的目标或者搜索完所有的点。

广度优先搜索是”先宽后深地访问顶点”的图搜索算法。

广度优先搜索(BFS)全过程

例如用下面的图结构,从顶点A开始搜索,直到搜索到顶点G。

广度优先搜索-图解过程1

可以知道,顶点A的相邻顶点有顶点B、顶点C、顶点D,这三个顶点,将它们视为开始搜索的顶点,加入队列。

广度优先搜索-图解过程2

根据队列数据结构(先进先出-FIFO)的原则,我们从顶点A的三个相邻顶点(B-C-D)中,选择最先进入队列的顶点B,移动到顶点B。

广度优先搜索-图解过程3

获取顶点B的相邻顶点(E-F),将他们加入队列。

广度优先搜索-图解过程4

根据队列的顺序,使用同样的方式:

到达顶点C,获取顶点C的相邻顶点(H),将它加入队列,接着(根据队列先进先出的原则)移动到顶点D。

获取顶点D的相邻顶点(I-J),将它加入队列,接着(根据队列先进先出的原则)移动到顶点E。

获取顶点E的相邻顶点(K),将它加入队列,接着(根据队列先进先出的原则)移动到顶点F。

获取顶点F的相邻顶点,发现没有相邻顶点,则进行下一个顶点H的出列。

获取顶点H的相邻顶点(G),将它加入队列,接着(根据队列先进先出的原则)移动到顶点I。

获取顶点I的相邻顶点,发现没有相邻顶点,则进行下一个顶点J的出列。

获取顶点J的相邻顶点(L),将它加入队列,接着(根据队列先进先出的原则)移动到顶点K。

获取顶点K的相邻顶点,发现没有相邻顶点,则进行下一个顶点G的出列。

获取顶点G,找到需要到达的目标,结束搜索。

广度优先搜索-图解过程5

实现广度优先搜索(BFS)

代码流程

  • 为了标记图的顶点,我们需要提供一个表示顶点颜色的常量对象。
    • 白色(WHITE):表示该顶点还没有被访问
    • 灰色(GREY):表示该顶点被访问过,但并未被探索过
    • 黑色(BLACK):表示该顶点被访问过且被完全探索过
1
2
3
4
5
6
// 广度优先算法中标记顶点的常量对象
const Colors = {
WHITE: 0, // 表示该顶点还没有被访问
GREY: 1, // 表示该顶点被访问过,但并未被探索过
BLACK: 2 // 表示该顶点被访问过且被完全探索过
};
  • 并且提供一个辅助方法,用于初始化每个顶点颜色。
1
2
3
4
5
6
7
8
9
10
11
12
/**
* 辅助方法:初始化每个顶点的颜色的函数
* @param {*} vertices 顶点列表
* @returns {*} 返回初始化顶点颜色后的对象
*/
const initializeColor = vertices => {
const color = {};
for (let i = 0; i < vertices.length; i++) {
color[vertices[i]] = Colors.WHITE;
}
return color;
};

接着便是广度优先搜索算法的完整代码思路:

  • 声明广度优先搜索算法的函数-breadthFirstSearch,接收三个参数,分别是graph(要遍历的图实例)、startVertex(开始顶点)、callback(回调函数)
  • 在函数内获取传入图实例(graph)的顶点列表、邻接表,并将图的顶点列表中的所有顶点初始化颜色为白色(表示该顶点还没有被访问)
  • 创建一个队列数据结构实例,并将startVertex(开始顶点)入队列。
  • 如果队列不为空,则进入循环,循环体内执行以下步骤:
    • 根据入队顺序,取出队列中的一个顶点,并获取这个顶点的邻接表,并将这个顶点的颜色标识为灰色(该顶点被访问过,但并未被探索过)
    • 如果这个顶点的邻接表不为空,则遍历这个顶点的邻接表中的顶点,遍历时,如果该邻接表的顶点是白色,则将它标识为灰色(该顶点被访问过,但并未被探索过),并将该邻接表顶点加入队列。
  • 这个顶点的邻接表探索完后,将这个顶点标识为黑色(已被访问且被完全探索)
  • 如果有传入回调函数,则执行该回调函数,回调函数会将这个顶点作为入参方法。

代码实现

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
/**
* 图的广度优先搜索算法
* 使用到的数据结构:队列
* 概念:先宽后深地访问顶点
* @param {*} graph 要进行遍历的图(Graph 类实例)
* @param {*} startVertex 开始顶点
* @param {function} callback 回调函数
*/
export const breadthFirstSearch = (graph, startVertex, callback) => {
const vertices = graph.getVertices(); // 获取传入参数的图,它的顶点列表
const adjList = graph.getAdjList(); // 获取传入参数的图,它的邻接表
const color = initializeColor(vertices); // 将图的顶点列表中的所有顶点初始化为白色
const queue = new Queue(); // 创建一个队列实例

queue.enqueue(startVertex); // 将开始顶点(startVertex)加入队列

while (!queue.isEmpty()) { // 如果队列不为空,则进入循环
const u = queue.dequeue(); // 按队列(先进先出)规则,取出队列里面存储的最前面的顶点,赋值给u
const neighbors = adjList.get(u); // 获取顶点u的邻接表
color[u] = Colors.GREY; // 标识顶点u为灰色(该顶点被访问过,但并未被探索过)
for (let i = 0; i < neighbors.length; i++) { // 循环遍历顶点u的邻接表
const w = neighbors[i]; // 取出邻接表的每个顶点,赋值给w
if (color[w] === Colors.WHITE) { // 如果当前顶点w是白色(顶点还没有被访问)
color[w] = Colors.GREY; // 则标识顶点w为灰色(该顶点被访问过,但并未被探索过)
queue.enqueue(w); // 将顶点w加入队列
}
}
color[u] = Colors.BLACK; // 此时顶点u与其相邻顶点已经被探索,将u标识为黑色(已被访问且被完全探索)
if (callback) { // 执行回调函数
callback(u);
}
}
};

代码用例

我们初始化一个图,用于测试广度优先搜索。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
let graph = new Graph();
const myVertices = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'];
for (let i = 0; i < myVertices.length; i++) {
graph.addVertex(myVertices[i]);
}
graph.addEdge("A", "B");
graph.addEdge("A", "C");
graph.addEdge("A", "D");
graph.addEdge("C", "D");
graph.addEdge("C", "G");
graph.addEdge("D", "G");
graph.addEdge("D", "H");
graph.addEdge("B", "E");
graph.addEdge("B", "F");
graph.addEdge("E", "I");

将这个实例图,用广度优先搜索算法打印出来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const printVertex = (value) => console.log('Visited vertex: ' + value);
breadthFirstSearch(graph, vertices[0], printVertex);


/**
*

// 最终打印结果
Visited vertex: A
Visited vertex: B
Visited vertex: C
Visited vertex: D
Visited vertex: E
Visited vertex: F
Visited vertex: G
Visited vertex: H
Visited vertex: I
*/

广度优先搜索算法(BFS)还可以做更多

广度优先搜索算法的工作原理了解之后,它还可以做更多事情,比如使用它来搜索图顶点的最短访问路径,或者图中某个顶点的前溯点。

下面是一段利用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
/**
* 使用BFS寻找图实例每个顶点最短路径和前溯点
* @param {*} graph 要进行遍历的图(Graph 类实例)
* @param {*} startVertex 开始顶点
*/
export const BFS = (graph, startVertex) => {
const vertices = graph.getVertices(); // 获取传入参数的图,它的顶点列表
const adjList = graph.getAdjList(); // 获取传入参数的图,它的邻接表
const color = initializeColor(vertices); // 将图的顶点列表中的所有顶点初始化为白色
const queue = new Queue(); // 创建一个队列实例
const distances = {}; // 存储每个顶点的距离
const predecessors = {}; // 存储前溯点

queue.enqueue(startVertex); // 将开始顶点(startVertex)加入队列

for (let i = 0; i < vertices.length; i++) { // 遍历图的顶点列表
distances[vertices[i]] = 0; // 初始化图中每一个顶点的距离为0
predecessors[vertices[i]] = null; // 初始化图中每一个顶点的前溯点为null
}
while (!queue.isEmpty()) { // 如果队列不为空,则进入循环
const u = queue.dequeue(); // 按队列(先进先出)规则,取出队列里面存储的最前面的顶点,赋值给u
const neighbors = adjList.get(u); // 获取顶点u的邻接表
color[u] = Colors.GREY; // 标识顶点u为灰色(该顶点被访问过,但并未被探索过)
for (let i = 0; i < neighbors.length; i++) { // 循环遍历顶点u的邻接表
const w = neighbors[i]; // 取出邻接表的每个顶点,赋值给w
if (color[w] === Colors.WHITE) { // 如果当前顶点w是白色(顶点还没有被访问)
color[w] = Colors.GREY; // 则标识顶点w为灰色(该顶点被访问过,但并未被探索过)
distances[w] = distances[u] + 1; // 给u顶点加1来增加v和w之间的距离(u是w的前溯点,distances[u]的值已经有了)
predecessors[w] = u; // 发现顶点u的邻点w时,则设置w的前溯点值为u
queue.enqueue(w); // 将顶点w加入队列
}
}
color[u] = Colors.BLACK; // 此时顶点u与其相邻顶点已经被探索,将u标识为黑色(已被访问且被完全探索)
}
// 最后,返回distances对象和predecessors对象
return {
distances,
predecessors
};
};

测试用例

我们初始化一个图,用于测试广度优先搜索。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
let graph = new Graph();
const myVertices = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'];
for (let i = 0; i < myVertices.length; i++) {
graph.addVertex(myVertices[i]);
}
graph.addEdge("A", "B");
graph.addEdge("A", "C");
graph.addEdge("A", "D");
graph.addEdge("C", "D");
graph.addEdge("C", "G");
graph.addEdge("D", "G");
graph.addEdge("D", "H");
graph.addEdge("B", "E");
graph.addEdge("B", "F");
graph.addEdge("E", "I");

将图实例传入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
const shortestPathA = BFS(graph, myVertices[0]);
console.log(shortestPathA.distances);
console.log(shortestPathA.predecessors);

/**
*
distances: [A: 0, B: 1, C: 1, D: 1, E: 2, F: 2, G: 2, H: 2 , I: 3]
predecessors: [A: null, B: "A", C: "A", D: "A", E: "B", F: "B", G: "C", H: "D", I: "E"]

距离(distances):
distances: [A: 0, B: 1, C: 1, D: 1, E: 2, F: 2, G: 2, H: 2 , I: 3]
顶点A到A的距离为0
顶点A到B的距离为1
顶点A到C的距离为1
顶点A到D的距离为1
顶点A到E的距离为2
顶点A到F的距离为2
顶点A到G的距离为2
顶点A到I的距离为3

前溯点(predecessors):
predecessors: [A: null, B: "A", C: "A", D: "A", E: "B", F: "B", G: "C", H: "D", I: "E"]
顶点A的前溯点为null
顶点B的前溯点为A
顶点C的前溯点为A
顶点D的前溯点为A
顶点E的前溯点为B
顶点F的前溯点为为B
顶点G的前溯点为C
顶点H的前溯点为D
顶点I的前溯点为E
*/

通过前溯点数组,我们还可以构建从顶点 A 到其他顶点的路径。

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
/**
* 通过前溯点数组,我们还可以构建从顶点 A 到其他顶点的路径。
*/
const fromVertex = myVertices[0]; // 用顶点A作为源顶点
// 遍历除过源顶点外的顶点
for (let i = 1; i < myVertices.length; i++) {
const toVertex = myVertices[i]; // 获取当前抵达的顶点的值
const path = new Stack(); // 创建一个栈来存储路径值
for (
let v = toVertex;
v !== fromVertex;
v = shortestPathA.predecessors[v]
) { // 追溯toVertex(当前抵达的顶点)到fromVertex(源顶点)的路径,变量v赋值为其前溯点的值
path.push(v); // v入栈
}
path.push(fromVertex); // 源顶点入栈
let s = path.pop(); // 创建一个s字符串,并将源顶点赋值给它(它是最后一个加入栈中的,所以是第一个被弹出的项)
while (!path.isEmpty()) { // 当栈是非空的
s += ' - ' + path.pop(); // 从栈中移出一个项并将其拼接到字符串 s 的后面
}
console.log(s); // 输出路径
// 最后,就得到了从顶点 A 到图中其他顶点的最短路径(衡量标准是边的数量)。
/**
* 打印结果
* A - B
A - C
A - D
A - B - E
A - B - F
A - C - G
A - D - H
A - B - E - I
*/
}

完整代码实现

附上上述所有代码的完整实现

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
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
import { Queue } from '/Queue/app.js';
import { Graph } from '/Graph/app.js';

/**
* 有两种算法可以对图进行遍历:广度优先搜索(breadth-first search,BFS)和深度优先搜索(depth-first search,DFS)。图遍历可以用来寻找特定的顶点或寻找两个顶点之间的路径,检查图是否连通,检查图是否含有环,等等。
*/

// 广度优先算法中标记顶点的常量对象
const Colors = {
WHITE: 0, // 表示该顶点还没有被访问
GREY: 1, // 表示该顶点被访问过,但并未被探索过
BLACK: 2 // 表示该顶点被访问过且被完全探索过
};

/**
* 辅助方法:初始化每个顶点的颜色的函数
* @param {*} vertices 顶点列表
* @returns {*} 返回初始化顶点颜色后的对象
*/
const initializeColor = vertices => {
const color = {};
for (let i = 0; i < vertices.length; i++) {
color[vertices[i]] = Colors.WHITE;
}
return color;
};
/**
* 图的广度优先搜索算法
* 使用到的数据结构:队列
* 概念:先宽后深地访问顶点
* @param {*} graph 要进行遍历的图(Graph 类实例)
* @param {*} startVertex 开始顶点
* @param {function} callback 回调函数
*/
export const breadthFirstSearch = (graph, startVertex, callback) => {
const vertices = graph.getVertices(); // 获取传入参数的图,它的顶点列表
const adjList = graph.getAdjList(); // 获取传入参数的图,它的邻接表
const color = initializeColor(vertices); // 将图的顶点列表中的所有顶点初始化为白色
const queue = new Queue(); // 创建一个队列实例

queue.enqueue(startVertex); // 将开始顶点(startVertex)加入队列

while (!queue.isEmpty()) { // 如果队列不为空,则进入循环
const u = queue.dequeue(); // 按队列(先进先出)规则,取出队列里面存储的最前面的顶点,赋值给u
const neighbors = adjList.get(u); // 获取顶点u的邻接表
color[u] = Colors.GREY; // 标识顶点u为灰色(该顶点被访问过,但并未被探索过)
for (let i = 0; i < neighbors.length; i++) { // 循环遍历顶点u的邻接表
const w = neighbors[i]; // 取出邻接表的每个顶点,赋值给w
if (color[w] === Colors.WHITE) { // 如果当前顶点w是白色(顶点还没有被访问)
color[w] = Colors.GREY; // 则标识顶点w为灰色(该顶点被访问过,但并未被探索过)
queue.enqueue(w); // 将顶点w加入队列
}
}
color[u] = Colors.BLACK; // 此时顶点u与其相邻顶点已经被探索,将u标识为黑色(已被访问且被完全探索)
if (callback) { // 执行回调函数
callback(u);
}
}
};


let graph = new Graph();
const myVertices = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'];
for (let i = 0; i < myVertices.length; i++) {
graph.addVertex(myVertices[i]);
}
graph.addEdge("A", "B");
graph.addEdge("A", "C");
graph.addEdge("A", "D");
graph.addEdge("C", "D");
graph.addEdge("C", "G");
graph.addEdge("D", "G");
graph.addEdge("D", "H");
graph.addEdge("B", "E");
graph.addEdge("B", "F");
graph.addEdge("E", "I");

const printVertex = (value) => console.log('Visited vertex: ' + value);
breadthFirstSearch(graph, vertices[0], printVertex);


/**
*

// 最终打印结果
Visited vertex: A
Visited vertex: B
Visited vertex: C
Visited vertex: D
Visited vertex: E
Visited vertex: F
Visited vertex: G
Visited vertex: H
Visited vertex: I
*/

/**
* 使用BFS寻找图实例每个顶点最短路径和前溯点
* @param {*} graph 要进行遍历的图(Graph 类实例)
* @param {*} startVertex 开始顶点
*/
export const BFS = (graph, startVertex) => {
const vertices = graph.getVertices(); // 获取传入参数的图,它的顶点列表
const adjList = graph.getAdjList(); // 获取传入参数的图,它的邻接表
const color = initializeColor(vertices); // 将图的顶点列表中的所有顶点初始化为白色
const queue = new Queue(); // 创建一个队列实例
const distances = {}; // 存储每个顶点的距离
const predecessors = {}; // 存储前溯点

queue.enqueue(startVertex); // 将开始顶点(startVertex)加入队列

for (let i = 0; i < vertices.length; i++) { // 遍历图的顶点列表
distances[vertices[i]] = 0; // 初始化图中每一个顶点的距离为0
predecessors[vertices[i]] = null; // 初始化图中每一个顶点的前溯点为null
}
while (!queue.isEmpty()) { // 如果队列不为空,则进入循环
const u = queue.dequeue(); // 按队列(先进先出)规则,取出队列里面存储的最前面的顶点,赋值给u
const neighbors = adjList.get(u); // 获取顶点u的邻接表
color[u] = Colors.GREY; // 标识顶点u为灰色(该顶点被访问过,但并未被探索过)
for (let i = 0; i < neighbors.length; i++) { // 循环遍历顶点u的邻接表
const w = neighbors[i]; // 取出邻接表的每个顶点,赋值给w
if (color[w] === Colors.WHITE) { // 如果当前顶点w是白色(顶点还没有被访问)
color[w] = Colors.GREY; // 则标识顶点w为灰色(该顶点被访问过,但并未被探索过)
distances[w] = distances[u] + 1; // 给u顶点加1来增加v和w之间的距离(u是w的前溯点,distances[u]的值已经有了)
predecessors[w] = u; // 发现顶点u的邻点w时,则设置w的前溯点值为u
queue.enqueue(w); // 将顶点w加入队列
}
}
color[u] = Colors.BLACK; // 此时顶点u与其相邻顶点已经被探索,将u标识为黑色(已被访问且被完全探索)
}
// 最后,返回distances对象和predecessors对象
return {
distances,
predecessors
};
};

const shortestPathA = BFS(graph, myVertices[0]);
console.log(shortestPathA.distances);
console.log(shortestPathA.predecessors);

/**
*
distances: [A: 0, B: 1, C: 1, D: 1, E: 2, F: 2, G: 2, H: 2 , I: 3]
predecessors: [A: null, B: "A", C: "A", D: "A", E: "B", F: "B", G: "C", H: "D", I: "E"]

距离(distances):
distances: [A: 0, B: 1, C: 1, D: 1, E: 2, F: 2, G: 2, H: 2 , I: 3]
顶点A到A的距离为0
顶点A到B的距离为1
顶点A到C的距离为1
顶点A到D的距离为1
顶点A到E的距离为2
顶点A到F的距离为2
顶点A到G的距离为2
顶点A到I的距离为3

前溯点(predecessors):
predecessors: [A: null, B: "A", C: "A", D: "A", E: "B", F: "B", G: "C", H: "D", I: "E"]
顶点A的前溯点为null
顶点B的前溯点为A
顶点C的前溯点为A
顶点D的前溯点为A
顶点E的前溯点为B
顶点F的前溯点为为B
顶点G的前溯点为C
顶点H的前溯点为D
顶点I的前溯点为E
*/

/**
* 通过前溯点数组,我们还可以构建从顶点 A 到其他顶点的路径。
*/
const fromVertex = myVertices[0]; // 用顶点A作为源顶点
// 遍历除过源顶点外的顶点
for (let i = 1; i < myVertices.length; i++) {
const toVertex = myVertices[i]; // 获取当前抵达的顶点的值
const path = new Stack(); // 创建一个栈来存储路径值
for (
let v = toVertex;
v !== fromVertex;
v = shortestPathA.predecessors[v]
) { // 追溯toVertex(当前抵达的顶点)到fromVertex(源顶点)的路径,变量v赋值为其前溯点的值
path.push(v); // v入栈
}
path.push(fromVertex); // 源顶点入栈
let s = path.pop(); // 创建一个s字符串,并将源顶点赋值给它(它是最后一个加入栈中的,所以是第一个被弹出的项)
while (!path.isEmpty()) { // 当栈是非空的
s += ' - ' + path.pop(); // 从栈中移出一个项并将其拼接到字符串 s 的后面
}
console.log(s); // 输出路径
// 最后,就得到了从顶点 A 到图中其他顶点的最短路径(衡量标准是边的数量)。
/**
* 打印结果
* A - B
A - C
A - D
A - B - E
A - B - F
A - C - G
A - D - H
A - B - E - I
*/
}

广度优先搜索
https://sothx.com/2021/04/22/BreadthFirstSearch/
作者
Sothx
发布于
2021年4月22日
许可协议