本文为：ES聚合算法原理深入解读：深度优先算法（DFS）和广度优先算法（BFS）第三篇

深度优先算法（DFS）和广度优先算法（BFS）：DFS 和 BFS 在 ES 中的应用（一）
深度优先算法（DFS）和广度优先算法（BFS）：深度优先搜索算法（二）
深度优先算法（DFS）和广度优先算法（BFS）：广度优先搜索算法（三）

2、广度优先搜索（Depth-First Search）

2.1 图的广度优先搜索

和树不同，图没有根节点，并且是可以回溯的，比如下图所示，为一个 8 节点的图搜索表示

其中： - **节点0** ：包含三个出度，分别指向其三个邻接点，分别为`节点1、节点2、节点3`，同时`节点0`也是`节点2`的邻接点。 - **节点1**：包含三个邻接点，分别为`节点2、节点4、节点5` - **节点2**：邻接点为`节点0、节点1、节点6`。 - **节点3**：邻接点为`节点6、节点7`。 - **节点4**：邻接点为`节点1`。 - **节点5**：邻接点为`节点1、节点2、节点4、节点6`。 - **节点6**：邻接点为`节点3`。 - **节点7**：邻接点为`节点6`

2.2 邻接表

下图为 2.1 中图搜索所示图的邻接表形式。可以看到，节点7、节点8、节点10 是没有任何出度和邻接点的。

## 2.3 邻接矩阵 下图为 2.1 中图搜索所示`图`的`邻接矩阵`表示

其中，纵坐标表示 出度节点，横坐标表示 邻接点

比如，下图中：

• 节点0：邻接点为节点1、节点2、节点3
• 节点3：邻接点为节点0、节点6

## 2.4 图的广度优先搜索遍历过程

2.4.1 队列

图的广度优先遍历是靠队列来完成的，我们首先创建一个空队列

### 2.4.2 Visited数组

我们借助 Visited数组，来标识当前节点 n 是否被访问过，空值代表 false.

2.4.3 遍历序列

准备一个空的遍历序列，用来存放最终生成的访问元素。

### 2.4.4 遍历过程 首先，图是没有根节点的，我们可以以任何节点作为其起始节点，下面我就以`节点0`为起始节点为例，演示一下图的广度优先搜索过程。

第1步
节点0入队列

**第2步** **`节点0`出队列，并且`节点0`的所有邻接点入队列**

**第3步** **`节点1`出队列，`节点1`的邻接点入队列，但是此时，`节点1`的邻接节点`节点2`已经被访问过了，因此`节点5、节点4`进队列**

**第4步**

**`节点2`出队列，`节点2`有两个邻接节点，其中`节点0`已经被访问，因此，`节点6`如队列**

**第5步** **`节点3`出队列，`节点3`有两个邻接节点，其中`节点6`已经被访问，因此，`节点7`入队列**

**第6步**

**`节点5`出队列，`节点5`有四个邻接节点均已被访问，此时无节点入队列。同理，`节点6、节点7`出队列，最终生成的遍历序列如下图所示**

2.5 动画演示

[video(video-kjGoS722-1654356792134)(type-csdn)(url-https://live.csdn.net/v/embed/213990)(image-https://video-community.csdnimg.cn/vod-84deb4/80b9c7c21a514634921a15aa65de1dd9/snapshots/91bd34eb5f254953a9bfe73fd22a8c5c-00002.jpg?auth_key=1654352465-043f64f72aa742878670d6a1026e045a-0-0edbbb37c05d01aeaec3711dcf095798)(title-BFS)]