算法技术手册（原书第2 版）

138

｜

第

6

章

广度优先搜索

不会进行任何回退。我们可以通过查看顶点的颜色（白色、灰色和黑色）

来查看进度，就像

深度优先搜索

那样。在

广度优先搜索

中，我们采用了相同的颜色定义。

为了和

深度优先搜索

直接进行对比，我们可以使用之前图

6-6

中相同的图，然后对比在

第

5

个结点被染为黑色（编号为

2

的顶点）后的情形，如图

6-10

所示。在图中显示的时刻，

搜索已经将源顶点

s

、距离

s

一条边的顶点

{1

，

6

和

8}

以及距离

s

两条边的顶点

2

染为

黑色。

图 6-10：广度优先搜索在图上 5 个顶点被染为黑色后的情形

剩下的距离

s

两条边的顶点

{3

，

5

，

7

，

14}

都位于队列

Q

中等待处理。而某些距离

s

三

条边的顶点也被访问过了，如

{10, 11}

，它们位于队列的尾端。注意，队列中的所有顶

点均为灰色，代表它们当前都处于活跃状态。

6.3.1 输入 / 输出

输入是图

G

= (

V

,

E

)

以及源顶点

s

∈

V

，代表起始位置。

广度优先搜索

生成了两个数组。

dist[v]

记录了从

s

到

v

最短路径上的边数，

pred[v]

则

记录了基于广度优先搜索排序中顶点

v

的前驱顶点。

pred[]

的

值记录了广度优先搜索的结

果。如果原始图是非连通的，那么对于所有源顶点不可达的顶点

w

，

pred[w]

的值为－

1

。