图-广度优先(BFS)

约束

此处讨论无向、无重复边、无自环、无权重的联通图。

图-广度优先搜索(BFS)

在图中优先同辈访问。

概念: 发现所有距离源点s为k的所有结节点后，才可以发现其他所有距离为k+1的节点。

广度优先搜索的前驱子图形成一棵树。

算法伪码

ADD-SET(e): 将元素 e 插入不重复元素集合中。
FIND-SET(e): 查找元素 e 是否在集合中。
ENQUEUE(Q, e): 把元素 e 插入队列 Q 尾部。
DEQUEUE(Q): 队列 Q 头出队。

Breadth-first search

#1     Q={} //Empty
#2     ENQUEUE(Q, s)
#3     ADD-SET(s)
#4     while Q is not empty
#5         u = DEQUEUE(Q)
#6         for each vertex(v) in G.Adj[u] //遍历 u 的孩子节点
#7             if v in FIND-SET(v)
#8                 continue; //已发现
#9             else 
#10                ENQUEUE(Q, v)
#11                ADD-SET(v)
#12        print u

举例

比如，有图Graph=G(V, E)如下：

A -- C -- E
|   /|
|  / |
 B   D -- G
     |   /
     |  /
      F

其 邻接链表(Adjacency List) 表示为：

A -- B -- C
B -- A -- C
C -- A -- B -- D -- E
D -- C -- F -- G
E -- C
F -- D -- G

领接矩阵(Adjacency Matrix) 表示为：

-	A	B	C	D	E	F	G
A	-	1	1	-	-	-	-
B	1	-	1	-	-	-	-
C	1	1	-	1	1	-	-
D	-	-	1	-	-	1	1
E	-	-	1	-	-	-	-
F	-	-	-	1	-	-	1
G	-	-	-	1	-	1	-

算法流程：

以 A 为源点。初始化时(#1 ~ #3)，将节点 A 加入队列(#2 执行后)，加入不重复元素集合(#3 执行后)。

此时队列是：Q{A}，不重复元素集合是： SET{A}。

while 循环次数	队头(#5 执行前)	出队后(#5 执行后)	入队(#6 ~ #11 执行后)	不重复元素集合(#6 ~ #11 执行后)
1	A	Q{}	Q{B, C}	SET{A, B, C}
2	B	Q{C}	Q{C}	SET{A, B, C}
3	C	Q{}	Q{D, E}	SET{A, B, C, D, E}
4	D	Q{E}	Q{E, F, G}	SET{A, B, C, D, E, F, G}
5	E	Q{F, G}	Q{F, G}	SET{A, B, C, D, E, F, G}
6	F	Q{G}	Q{G}	SET{A, B, C, D, E, F, G}
7	G	Q{}	Q{}	SET{A, B, C, D, E, F, G}

注：入队的顺序影响了后续出队的顺序。算法伪码中具有相同深度孩子节点的入队(#10) 会影响到后续的出队(#5)。

此例中，构造出的树如下所示：

L0 -----   A   --------- L0
          / \
L1 ---   B   C   ------- L1
            / \
L2 -----   D   E   ----- L2
          / \
L3 ---   F   G   ------- L3

其广度优先遍历的顺序是，L0 -> L1 -> L2 -> L3，相同层的节点顺序可以不同。如 L1 层，其 B、C 深度为 1 ，顺序可以是 先 B 后 C，亦可是先 C 后 B 等其他符合“广度优先”的顺序。

要点

• 从源点出发，按照 “广度” 先发现距离源点深度为 k 的所有节点，之后再发现距离源点深度为 k+1的。
• 重要定理：广度优先搜索计算出来的即是最短路径。

应用

• 使用广度优先搜索算法(BFS)可以查找出图中的 单源最短路径(Single-Source Shortest Paths)、每对顶点间的最短路径(All-Pairs Shortest Paths) 等。
• 使用 BFS 可以构造出图的最小生成树。

其它

• 与深度优先搜索原理类似，此处采用了 “队列” 的 “先进先出” 特性来完成 “广度” 的遍历。

参考

[1] Thomars H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein. Introduction to Algorithms.