宽度优先搜索 BFS

宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。

已知图G=(V,E)和一个源顶点s，宽度优先搜索以一种系统的方式探寻G的边，从而“发现”s所能到达的所有顶点，并计算s到所有这些顶点的距离(最少边数)，该算法同时能生成一棵根为s且包括所有可达顶点的宽度优先树。对从s可达的任意顶点v，宽度优先树中从s到v的路径对应于图G中从s到v的最短路径，即包含最小边数的路径。该算法对有向图和无向图同样适用。

之所以称之为宽度优先算法，是因为算法自始至终一直通过已找到和末找到顶点之间的边界向外扩展，就是说，算法首先搜索和s距离为k的所有顶点，然后再去搜索和S距离为k+l的其他顶点。

为了保持搜索的轨迹，宽度优先搜索为每个顶点着色：白色、灰色或黑色。算法开始前所有顶点都是白色，随着搜索的进行，各顶点会逐渐变成灰色，然后成为黑色。在搜索中第一次碰到一顶点时，我们说该顶点被发现，此时该顶点变为非白色顶点。因此，灰色和黑色顶点都已被发现，但是，宽度优先搜索算法对它们加以区分以保证搜索以宽度优先的方式执行。若(u,v)∈E且顶点u为黑色，那么顶点v要么是灰色，要么是黑色，就是说，所有和黑色顶点邻接的顶点都已被发现。灰色顶点可以与一些白色顶点相邻接，它们代表着已找到和未找到顶点之间的边界。

在宽度优先搜索过程中建立了一棵宽度优先树，起始时只包含根节点，即源顶点s.在扫描已发现顶点u的邻接表的过程中每发现一个白色顶点v，该顶点v及边(u,v)就被添加到树中。在宽度优先树中，我们称结点u是结点v的先辈或父母结点。因为一个结点至多只能被发现一次，因此它最多只能有--个父母结点。相对根结点来说祖先和后裔关系的定义和通常一样：如果u处于树中从根s到结点v的路径中，那么u称为v的祖先，v是u的后裔。

下面的宽度优先搜索过程BFS假定输入图G=(V,E)采用邻接表表示，对于图中的每个顶点还采用了几种附加的数据结构，对每个顶点u∈V，其色彩存储于变量color[u]中，结点u的父母存于变量π[u]中。如果u没有父母(例如u=s或u还没有被检索到)，则 π[u]=NIL，由算法算出的源点s和顶点u之间的距离存于变量d[u]中，算法中使用了一个先进先出队列Q来存放灰色节点集合。其中head[Q]表示队列Q的队头元素，Enqueue(Q,v)表示将元素v入队， Dequeue(Q)表示对头元素出队；Adj[u]表示图中和u相邻的节点集合。

  procedure BFS(G,S);
   begin
1.   for 每个节点u∈V[G]-{s} do
        begin
2.        color[u]←White;
3.        d[u]←∞;
4.        π[u]←NIL;
        end;
5.   color[s]←Gray;
6.   d[s]←0;
7.   π[s]←NIL;
8.   Q←{s}
9.   while Q≠φ do
       begin
10.      u←head[Q];
11.      for 每个节点v∈Adj[u] do
12.        if color[v]=White then
              begin
13.             color[v]←Gray;        
14.             d[v]←d[v]+1;
15.             π[v]←u;
16.             Enqueue(Q,v);
              end;   
17.      Dequeue(Q);
18.      color[u]←Black;
       end;
   end; 

图1展示了用BFS在例图上的搜索过程。黑色边是由BFS产生的树枝。每个节点u内的值为d[u]，图中所示的队列Q是第9-18行while循环中每次迭代起始时的队列。队列中每个结点下面是该结点与源结点的距离。

图1 BFS在一个无向图上的执行过程

过程BFS按如下方式执行，第1-4行置每个结点为白色，置d[u]为无穷大，每个结点的父母置为NIL，第5行置源结点S为灰色，即意味着过程开始时源结点已被发现。第6行初始化d[s]为0，第7行置源结点的父母结点为NIL，第8行初始化队列0，使其仅含源结点s，以后Q队列中仅包含灰色结点的集合。

程序的主循环在9-18行中，只要队列Q中还有灰色结点，即那些已被发现但还没有完全搜索其邻接表的结点，循环将一直进行下去。第10行确定队列头的灰色结点为u。第11-16行的循环考察u的邻接表中的每一个顶点v。如果v是白色结点，那么该结点还没有被发现过，算法通过执行第13-16行发现该结点。首先它被置为灰色，距离d[v]置为d[u]+1，而后u被记为该节点的父母，最后它被放在队列Q的队尾。当结点u的邻接表中的所有结点都被检索后，第17-18行使u弹出队列并置成黑色。

分析

在证明宽度优先搜索的各种性质之前，我们先做一些相对简单的工作——分析算法在图G=(V,E)之上的运行时间。在初始化后，再没有任何结点又被置为白色。因此第12行的测试保证每个结点至多只能迸人队列一次，因而至多只能弹出队列一次。入队和出队操作需要O(1)的时间，因此队列操作所占用的全部时间为O(V)，因为只有当每个顶点将被弹出队列时才会查找其邻接表，因此每个顶点的邻接表至多被扫描一次。因为所有邻接表的长度和为Q(E)，所以扫描所有邻接表所花费时间至多为O(E)。初始化操作的开销为O(V)，因此过程BFS的全部运行时间为O(V+E)，由此可见，宽度优先搜索的运行时间是图的邻接表大小的一个线性函数。

最短路径

在本部分的开始，我们讲过，对于一个图G=(V,E)，宽度优先搜索算法可以得到从已知源结点s∈V到每个可达结点的距离，我们定义最短路径长度δ(s,v)为从顶点s到顶点v的路径中具有最少边数的路径所包含的边数，若从s到v没有通路则为∞。具有这一距离δ(s,v)的路径即为从s到v的最短路径（后文我们将把最短路径推广到赋权图，其中每边都有一个实型的权值，一条路径的权是组成该路径所有边的权值之和，目前讨论的图都不是赋权图）。在证明宽度优先搜索计算出的就是最短路径长度之前，我们先看一下最短路径长度的一个重要性质。

引理1

设G=(V,E)是一个有向图或无向图，s∈V为G的任意一个结点，则对任意边(u,v)∈E,

δ(s,v)≤δ(s,u)+1

证明:

如果从顶点s可达顶点u，则从s也可达v。在这种情况下从s到v的最短路径不可能比从s到u的最短路径加上边(u,v)更长，因此不等式成立；如果从s不可达顶点u，则δ(s,v)=∞，不等式仍然成立。

我们试图说明对每个顶点v∈V，BFS过程算出的d[v]=δ(s,v)，下面我们首先证明d[v]是δ(s,v)的上界。

引理2

设G=(V,E)是一个有向或无向图，并假设算法BFS从G中一已知源结点s∈V开始执行，在执行终止时，对每个顶点v∈V，变量d[v]的值满足：d[v]≥δ(s,v)。

证明:

我们对一个顶点进入队列Q的次数进行归纳，我们归纳前假设在所有顶点v∈V，d[v]≥δ(s,v)成立。

归纳的基础是BFS过程第8行当结点s被放入队列Q后的情形，这时归纳假设成立，因为对于任意结点v∈V-{s},d[s]=0=δ(s,s)且d[v]=∞≥δ(s,v)。

然后进行归纳，考虑从顶点u开始的搜索中发现一白色顶点v，按归纳假设，d[u]≥δ(s,u)。从过程第14行的赋值语句以及引理1可知

d[v]=d[u]+1≥δ(s,u)+1≥δ(s,v)

然后，结点v被插入队列Q中。它不会再次被插入队列，因为它已被置为灰色，而第13-16行的then子句只对白色结点进行操作，这样d[v]的值就不会改变，所以归纳假设成立。

为了证明d[v]=δ(s,v)，首先我们必须更精确地展示在BFS执行过程中是如何对队列进行操作的，下面一个引理说明无论何时，队列中的结点至多有两个不同的d值。

引理3

假设过程BFS在图G=(V,E)之上的执行过程中，队列Q包含如下结点<v₁,v₂,...,v_r>，其中v₁是队列Q的头，v_r是队列的尾，则d[v_i]≤d[v₁]+1且d[v_i]≤d[v_i+1], i=1,2,..,r-1。

证明:

证明过程是对队列操作的次数进行归纳。初始时，队列仅包含顶点s，引理自然正确。

下面进行归纳，我们必须证明在压入和弹出一个顶点后引理仍然成立。如果队列的头v₁被弹出队列，新的队头为v₂(如果此时队列为空，引理无疑成立)，所以有d[v_r]≤d[v₁]+1≤d[v₂]+1，余下的不等式依然成立，因此v₂为队头时引理成立。要插入一个结点入队列需仔细分析过程BFS，在BFS的第16行，当顶点v加入队列成为v_r+1时，队列头v₁实际上就是正在扫描其邻接表的顶点u，因此有d[v_r+1]=d[v]=d[u]+1=d[v₁]+1，这时同样有d[v_r]≤d[v₁]+1=d[u]+1=d[v]=d[v_r+1]，余下的不等式d[v_r]≤d[v_r+1]仍然成立，因此当结点v插入队列时引理同样正确。

现在我们可以证明宽度优先搜索算法能够正确地计算出最短路径长度。

定理1 宽度优先搜索的正确性

设G=(V,E)是一个有向图或无向图，并假设过程BFS从G上某顶点s∈V开始执行，则在执行过程中，BFS可以发现源结点s可达的每一个结点v∈V，在运行终止时，对任意v∈V,d[v]=δ(s,v)。此外，对任意从s可达的节点v≠s，从s到v的最短路径之一是从s到π[v]的最短路径再加上边(π[v],v)。

证明:

我们先证明结点v是从s不可达的情形。由引理2，d[v]≥δ(s,v)=∞，根据过程第14行，顶点v不可能有一个有限的d[v]值，由归纳可知，不可能有满足下列条件的第一个顶点存在：该顶点的d值被过程的第14行语句置为∞，因此仅对有有限d值的顶点，第14行语句才会被执行。所以若v是不可达的话，它将不会在搜索中被发现。

证明主要是对由s可达的顶点来说的。设V_k表示和s距离为k的顶点集合，即V_k={v∈V:δ(s,v)=k}。证明过程为对k进行归纳。作为归纳假设，我们假定对于每一个顶点v∈V_k，在BFS的执行中只有某一特定时刻满足：

• 结点v为灰色；
• d[v]被置为k；
• 如果v≠s，则对于某个u∈V_k-1，π[v]被置为u；
• v被插入队列Q中；

正如我们先前所述，至多只有一个特定时刻满足上述条件。

归纳的初始情形为k=0，此时V₀={s}，因为显然源结点s是唯一和s距离为0的结点，在初始化过程中，s被置为灰色，d[s]被置为0，且s被放人队列Q中，所以归纳假设成立。

下面进行归纳，我们须注意除非到算法终止，队列Q不为空，而且一旦某结点u被插入队列，d[u]和π[u]都不再改变。根据引理3可知如果在算法过程中结点按次序v₁,v₂,...,v_r被插入队列，那么相应的距离序列是单调递增的：d[v_i]≤d[v_i+1]，i=1,2,...,r-1。

现在我们考虑任意结点v∈V_k，k≥1。根据单调性和d[v]≥k(由引理2)和归纳假设，可知如果v能够被发现，则必在V_k-1中的所有结点进入队列之后。

由δ(s,v)=k，可知从s到v有一条具有k边的通路，因此必存在某结点u∈V_k-1，且(u,v)∈E。不失一般性，设u是满足条件的第一个灰色节点(根据归纳可知集合V_k-1中的所有结点都被置为灰色)，BFS把每一个灰色结点放入队列中，这样由第10行可知结点u最终必然会作为队头出现。当已成为队头时，它的邻接表将被扫描就会发现结点v（结点v不可能在此之前被发现，因为它不与V_j(j<k-1)中的任何结点相邻接，否则v不可能属于V_k，并且根据假定，u是和v相邻接的V_k-1中被发现的第一个结点)。第13行置v为灰色，第14行置d[v]=d[u]+l=k，第15行置π[v]为u，第16行把v插入队列中。由于v是V_k中的任意结点，因此证明归纳假设成立。

在结束定理的证明前，我们注意到如果v∈V_k，则据我们所知可得π[v]∈V_k-1，这样我们就得到了一条从s到v的最短路径：即为从s到π[v]的最短路径再通过边(π[v],v)。

宽度优先树

过程BFS在搜索图的同时建立了一棵宽度优先树，如图1所示，这棵树是由每个结点的π域所表示。我们正式定义先辈子图如下，对于图G=(V,E)，源顶点为s，其先辈子图G_π=(V_π,E_π)满足：

V_π={v∈V:π[v]≠NIL}∪{s}

且

E_π={(π[v],v)∈E:v∈V_π-{s}}

如果V_π由从s可达的顶点构成，那么先辈子图G_π是一棵宽度优先树，并且对于所有v∈V_π，G_π中唯一的由s到v的简单路径也同样是G中从s到v的一条最短路径。由于它互相连通，且|E_π|=|V_π|-1(由树的性质)，所以宽度优先树事实上就是一棵树，E_π中的边称为树枝。

当BFS从图G的源结点s开始执行后，下面的引理说明先辈子图是一棵宽度优先树。

引理4

当过程BFS应用于某一有向或无向图G=(V,E)时，该过程同时建立的π域满足条件：其先辈子图G_π=(V_π,E_π)是一棵宽度优先树。

证明：

过程BFS的第15行语句对(u,v)∈E且δ(s,v)<∞(即v从s可达)置π[v]=u，因此V_π是由V中从v可达的顶点所组成，由于G_π形成一棵树，所以它包含从s到V_π中每一结点的唯一路径，由定理1进行归纳，我们可知其每条路径都是一条最短路径。(证毕)

下面的过程将打印出从S到v的最短路径上的所有结点，假定已经运行完BFS并得出了最短路径树。

 procedure Print_Path(G,s,v);
  begin
1.  if v=s 
2.     then write(s)
3.     else if π[v]=nil 
4.             then writeln('no path from ',s,' to ',v, 'exists.')
               else 
                 begin
5.                 Print_Path(G,s,π[v]);
6.                 write(v);
                 end; 
  end;

因为每次递归调用的路径都比前一次调用少一个顶点，所以该过程的运行时间是关于打印路径上顶点数的一个线性函数。