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

图算法

｜

139

图算法

6.3.2 使用环境

广度优先搜索

将待处理的顶点存放在队列中，因此需要

O

(

V

)

的存储。

广度优先搜索

可

以保证在图中找到一条最短路径（有可能存在多条），其中的顶点都在“行进中”生成（详

见第

7

章）。事实上，生成的广度优先树中的所有从

s

出发的路径（按边数来说）都是

最短路径。

6.3.3 解决方案

例

6-2

展示了

广度优先搜索

的

C++

实现。

广度优先搜索

在队列中存储其状态，因此不需

要任何递归函数调用。

例

6-2

：广度优先搜索实现

/**

*

从源

顶点开始进行广度优先搜索，对图中所有顶点计算

BFS

距离和前驱顶点

*/

void bfsSearch (Graph const &graph, int s, /*

输入

*/

vector<int> &dist, vector<int> &pred) /*

输出

*/

{

//

初始化

dist

和

pred

以标记所有顶点为未被访问

//

从

s

开始，将其标记为灰色，因为它的所有邻接顶点还未被访问

const int n = graph.numVertices();

pred.assign(n,

－

1);

dist.assign(n, numeric_limits<int>::max());

vector<vertexColor> color (n, White);

dist[s] = 0;

color[s] = Gray;

queue<int> q;

q.push(s);

while ...