广度优先搜索

广度优先搜索（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;

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