阅读 ‧ 电子书库

广度优先搜索

广度优先搜索（图6-11）使用了和深度优先搜索一种不同的方法来搜索图。广度优先搜索系统地在图中搜索顶点，在搜索离源点s的距离为k+1条边的顶点之前，所有的离源点s距离为k条边的顶点都已经被访问。广度优先搜索不会访问图中那些源点不可达的顶点。

广度优先搜索不会进行任何回溯。我们可以通过查看顶点的颜色来查看进度，就像深度优先搜索那样。事实上，在广度优先搜索中，我们使用同样的颜色和定义。为了和深度优先搜索进行直接对比，我们使用一个类似的计数器，用来记录顶点第一次访问和最后一次访问的时刻。如图6-8所示，在相同的时间（例如，当计数器达到18时），广度优先搜索能够前进到图6-12的状态，即顶点12被标记为灰色。注意深度优先搜索已经处理顶点{1，6，8}，这些顶点都是离源点s一条边的距离，以及顶点{2，3}，它们离源点s两条边的距离，还有顶点{7，14，5}，它们在队列中等待被处理。有些顶点离源点s三条边距离，例如{11，10，12，4}，已经被访问过了，虽然广度优先搜索还没有处理这些顶点。注意队列中的所有顶点都被染成灰色，表示它们现在的状态。

输入/输出

输入

广告：个人专属 VPN，独立 IP，无限流量，多机房切换，还可以屏蔽广告和恶意软件，每月最低仅 5 美元

图G=(V,E)以及一个源点s∈V。n表示G中的顶点数。

输出

广度优先搜索得到了两个数组。dist[v]是从s到v的最短路径上的边数。pred[v]是在广度优先搜索中v的前驱顶点。根据pred[]的值，我们可以得到广度优先树，如果原始图是非连通的，那么对于所有源点不可达的顶点w，其pred[w]值是-1。

假设

此算法适用于有向图和无向图。