图搜索算法：广度优先查找

gaunthan Posted on Feb 17 2017

? Searching ? ? Algorithm ?

> **广度优先查找**(Breadth First Search, BFS)与[深度优先查找](http://leanote.com/blog/post/58a65061ab64414b060026d9)一样，是穷举查找、无信息图查找算法的一种，用来系统地遍历图中的所有顶点和边。

## 思想
如果说深度优先查找遍历表现出来的是一种勇气（该算法尽可能地离“家”远些），那么广度优先查找遍历表现出来的则是一种谨慎。它按照一种同心圆的方式，首先访问所有和初始顶点邻接的顶点，然后是离它再远一步的所有未访问顶点，以此类推，直到所有与初始顶点在同一个连通分量中的顶点都访问过了为止。如果仍然存在未被访问的顶点，该算法必须从图的其他连通分量中的任意顶点重新开始。

广度优先查找需要借用到队列来实现。该队列先从遍历的初始顶点开始，将该顶点标记为已访问。在每次迭代的时候，该算法找到所有和队头顶点邻接的未访问顶点，把它们标记为已访问，再把它们入队。然后，将队头顶点从队列中除去。

## 示例
示例如下：
![](https://leanote.com/api/file/getImage?fileId=58a6613eab64414b06002905)[^BFS Sample]

[^BFS Sample]:[C++ :: Breadth-first search algorithm (BFS)](http://nbangla.blogspot.com/2012/12/c-breadth-first-algorithm-bfs.html).

## 伪代码
以下是深度优先查找遍历的伪代码，它能够输出每个顶点第一次被遍历的顺序：
```cpp
// 实现给定图的广度优先查找遍历
// @input   图G = <V, E>
// @output  图G的顶点，按照被访问到的先后次序用整数标记
BFS(G)
    将V中的每个顶点标记为0，表示还未被访问
    count = 0
    for each v vertex in V do
        if v is marked with 0
            bfs(v)

// 访问所有和v相邻接的未访问顶点，然后按照count的值给它们标序
bfs(v)
    ++count; mark v with count
    initialize a queue with v
    while the queue is not empty do
        for each vertex w in V adjacant to the front vertex do
            if w if marked with 0
                ++count; mark w with count
                add w to the queue
        remove the front vertex from the queue
```

## 效率分析
广度优先查找和深度优先查找的效率是相同的：

- 对于邻接矩阵表示法，它属于$\theta(|V|^2)$；
- 而对于邻接链表表示法，它属于$\theta(|V|+|E|)$。

和深度优先查找不同的是，广度优先查找只产生顶点的一种排序。因为队列是一种FIFO结构，所以顶点入队的次序和它们出队的次序是相同的。

## 应用
### 二叉树的层次遍历
二叉树有三种遍历方式：先序遍历、中序遍历以及后序遍历。实际上，我们还可以实现一种结构化的遍历方式：层次遍历。层次遍历在实现二叉树的可视化时非常有帮助。树的层次遍历算法实际上就是广度优先查找遍历。

### 检查图的连通性和无环性
BFS也可以检查图的连通性和无环性，做法在本质上和DFS是一样的。

### 求两个给定顶点的最少边路径
从两个给定顶点中的一个开始BFS遍历，一旦访问到了另一个顶点就结束。这时候我们的遍历顺序将生成一棵树，该树的根结点是起始顶点。树根到另一个给定顶点的路径，就是所求的、边数量最少的路径。

## See Also

- [图搜索算法：深度优先查找](http://leanote.com/blog/post/58a65061ab64414b060026d9)

## References

- 莱维汀, A.). 算法设计与分析基础(第3版)[M]. 清华大学出版社, 2015.