Day-28 Breadth-First Search(BFS), 广度优先搜寻

BFS简介

BFS是用来遍历一张图的最简单演算法，也是很多在图论演算法的原型，许多演算法都是基於BFS，像是Prim最小生成树，Dijkstra演算法等等。

给定一张图 $G=(V,E)$ ，和一个节点s，BFS可以走访s能够到达的所有节点v，并且能够纪录s到各个节点的最少边数，也就是最短距离，同时会产生出一棵BST Tree。这个数会以s作为树的根结点，并且包含s能够到达的所有节点v。BST可以用在有向图，也可以用在无向图中。

为了方面演示这个演算法，我们将结点以三个颜色做为表示，白色，灰色，黑色做为表示。所有节点在一开始的时候都标记为白色，在BST持续进行的过程，这些节点会变成灰色或是黑色。在遍历的过程中，第一次遇到的节点就称为该节点被发现，并且同时节点的颜色发生改变，黑色和灰色皆为已经被发现的节点。

白色表示还没被其他节点发现的节点，灰色表示被其他节点发现的节点，且被推入Queue中，黑色表示被其他节点发现得节点，且已经被Pop出Queue。

下面为BFS的虚拟码，假设给定图 $G=(V,E)$ ，以邻接矩阵表示，每一个节点作为物件表示，节点的颜色储存在 $u.color$ 中， $u.\pi$ 储存前驱节点，如果不存在节点，则表示为NULL， $u.d$ 纪录s到u的距离。这个演算法还需要一个Queue来储存灰色的节点。

BFS(G, s)
for each vertex u ∈ G.V - {s}
  u.color = WHITE
  u.d = ∞
  u.π = NULL
s.color = GRAY
s.d = 0
s.π = NULL
Q = ∅
ENQUEUE(Q, s)
while Q != ∅
u = DEQUEUE(Q)
for each v ∈ G.Adj[u]
  if v.color == WHITE
     v.color = GRAY
     v.d = u.d + 1
     v.π = u
     ENQUEUE(Q, v)
u.color = BLACK

(a)一开始从s节点开始，s节点被发现，标记为灰色，同时推入Queue中。
(b)将s弹出Queue，弹出的节点可以看做是目前所在节点，并将s标记为黑色，接着w, r被发现，标记成灰色，同时推入Queue中。1表示s一步就能到达的节点，储存到v.d中。
(c)将w弹出Queue，并将w标记成黑色，可以将黑色视为目前所在的节点，接着，t和x被发现，标记成灰色，同时推入Queue。2表示s走两步可以到的节点，步数储存到v.d中。
(d)将r弹出Queue，并将r标记成黑色，r所在的地方发现到节点v，标记成灰色，并推入Queue，v是s两步可以走到的节点，步数储存到v.d中。
(e)将t弹出Queue，并将t标记成黑色，t所在的地方发现到节点u，标记成灰色，并推入Queue，u是s走三步可以走到的节点，步数储存到v.d中。
(f)将x弹出Queue，并将x标记成黑色，x所在的地方发现到节点y，标记成灰色，并推入Queue，y是s走三步可以走到的节点，步数储存到v.d中。
(g)将v弹出Queue，并将v标记成黑色，v所在的地方发现不到任何节点。
(h)将u弹出Queue，并将u标记成黑色，u所在的地方发现到y，但y已经在Queue中，故没有新的节点被推入Queue。
(i)将y弹出Queue，并将y标记成黑色，y所在的地方发现不到任何节点。

在BFS中，一开始构建出的BFS Tree只会有一个根结点s，在遍历过程中看到u节点的邻接串列时，每当发现到一个白色节点v，就将结点v和 $(u,v)$ 边加入到树中。BFS Tree中，称u节点是v节点的前驱点或是父节点。

在虚拟码1到4行中，我们先将s节点从G.V集合中移出，并遍历除了s的所有节点，都将他标记成白色，并将每一个节点的u.d标记成无限，无限的概念就是走不到的意思，引申为还没走到的节点，并将每一个父节点标记成NULL。

在第5行将s标记成灰色，因为在BST最一开始时，我们便发现到s了，并且只有s是没有被标记成白色的，第6行和第7行初始化s。第8,9行初始化Queue，Queue的初始状态下，里面只有s。

第10行到18行while回圈一直执行到没有灰色节点为止，在第一次迭代，只有s节点是灰色的，Queue中也是只有s节点，直到第11行Pop出来。

第12行到17行for回圈对u节点的邻接串列中每一个节点v进行探测，如果v为白色，表示还没被发现，使用第14行到17行来发现节点，将刚刚白色的v节点涂上灰色，并将v.d = u.d + 1，改变距离，并将u当作是v的父节点，然後插入到Queue的尾端。

在第18行，检查u的邻接串列中所有节点後，将u节点标记成黑色。

以树的形式来看BFS，就可以发现到广度优先的特性了，我们可以观察到我们是一层接着一层的去遍历整棵树，而这个特性可以给予我们到某一个节点的最短路径，BFS好处在於可以告诉我们哪一些节点是s抵达不了的。

效率

从上面的例子观察到，每一个节点最多就是出队和入队各一次，而Queue的入队和出队操作皆为 $O(1)$ ，总共在集合G.V中有|V|个节点，因此时间复杂度为 $O(V)$ 。BFS只有在节点出队的时候才会对节点对应到的邻接串列进行遍历，而无论是有向图，还是无向图，他们的邻接串列的长度皆为 $\Theta(E)$ ，而整体BFS所需要的时间复杂度为 $O(V) + O(E) = O(V + E)$ ，而这是一个线性函数。