【小算法】图的遍历之广度优先(BFS)
谈到算法，图的操作是避免不了。
而我们一般谈到图时，又必定会谈到图的遍历。
图的遍历通常有 2 种，深度优先(DFS) 和广度优先(BFS)。
深度优先可以阅读我这篇博文：【小算法】图的遍历之深度优先(DFS)
本篇博文讲解广度优先(BFS)。
图的表示
图有两种表示方式
1. 临接矩阵
其实就是一个权重矩阵，用 1 代表两个结点有连接，0 表示没有连接，这样的表示方式通俗易懂，特别适合稠密图，也就是大多数结点是亮亮连接的情况。
2. 临接表
用一个数组储存所有的顶点的信息，每个顶点又用一个链表或者是数组存放与它相临的结点的信息。
这样的表示方式特别适合稀疏图，也就是比较少的结点之间相互有连接。
本文示例代码用 Python 表示，为了简便，用临接表这种形式表示
BFS 算法思路
其实 BFS 的思路非常简单。
如果你哪天钱包忘记在哪里了，以 BFS 的思路就是有层次地搜索。
先每个房间快速地瞄一眼，如果没有发现的话，那么就在每个房间的床上、桌子上快速瞄一眼。
如果还是不行的话，再在每个家具的每个柜子里快速瞄一眼。
然后，按照这样一层一层进行下去。
DFS 图例
上面是一张图，如果要遍历图中所有的结点，又不重复。
在实际编码中，如果要用 BFS 的方式去遍历一个图的话，通常我们会用一个队列来动态保存陆续访问的结点。
我们首先选择 A.
所以 A 先入队列。
A 有 2 个临接结点 B 和 C,所以 B 和 C 依次入队列。
并且将 A 从队列中弹出。
A 结点出队后，现在队列首个元素是 B 结点，B 结点有 4 个临接点 A、C、D、F。
因为 A 和 C 已经入队列过一次，所以不能再入，因此将 D、F 入列。
最后，将 B 结点及时弹出来。
B 结点弹出来后，C 结点就是队列的首元素，它有 A、B、E 3 个临结点，但是 A 和 B 已经入队列访问过，所以它只需要将 E 入列就好了。
然后，C 将自己弹出来。
队列首元素就变成了 D.
由于 D 结点所有的临接点都已经入队列过了，代表访问过了，所以它弹出自己就好。
后面的 F 和 E 也是这样的逻辑，就不赘述了。
最后，队列所有的元素弹出后，也没有新的元素可以再入列的时候，也就说明完整的 BFS 过程结束了。
巧妙地利用队列先进先出(FIFO)的特性用来保存遍历的结点痕迹，最终实现了无重复也无遗漏的图的遍历，这种算法思想非常的赞。
下面用代码示例验证一下，python 版本是 3.6
Python 代码
bfs.py
import queue
# G 是临接表的方式表达图形
G={}
G[0] = {1,2}
G[1] = {2,3,5}
G[2] = {0,1,3}
G[3] = {2,4,5}
G[4] = {1,3,5}
G[5] = {1,3,4}
# 记录访问过的结点
visited = [False,False,False,False,False,False]
# 结点的别名
names=['A','B','C','D','E','F']
vertex_queue = queue.Queue()
def bfs(root):
vertex_queue.put(root)
visited[root] = True
while not vertex_queue.empty():
v = vertex_queue.get()
print("----->",names[v])
for i,value in enumerate(G[v]):
# 已经入过 queue 的结点就不用再入
if not visited[value]:
visited[value] = True
vertex_queue.put(value)
if __name__ == "__main__":
# 打印图
print("Graphy:",G)
#dfs(0)
bfs(0)最终结果如下：
Graphy: {0: {1, 2}, 1: {2, 3, 5}, 2: {0, 1, 3}, 3: {2, 4, 5}, 4: {1, 3, 5}, 5: {1, 3, 4}}
---> A
---> B
---> C
---> D
---> F
---> E可以看到，代码可以正常执行，大家亲手实践一下吧。