1、宽度优先搜索 BFS宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra 单源最短路径算法和 Prim 最小生成树算法都采用了和宽度优先搜索类似的思想。已知图 G=(V,E)和一个源顶点 s，宽度优先搜索以一种系统的方式探寻 G 的边，从而“发现”s 所能到达的所有顶点，并计算 s 到所有这些顶点的距离(最少边数 )，该算法同时能生成一棵根为 s 且包括所有可达顶点的宽度优先树。对从 s 可达的任意顶点 v，宽度优先树中从 s 到 v 的路径对应于图 G 中从 s 到 v的最短路径，即包含最小边数的路径。该算法对有向图和无向图同
2、样适用。之所以称之为宽度优先算法，是因为算法自始至终一直通过已找到和末找到顶点之间的边界向外扩展，就是说，算法首先搜索和 s 距离为 k 的所有顶点，然后再去搜索和 S 距离为 k+l 的其他顶点。为了保持搜索的轨迹，宽度优先搜索为每个顶点着色：白色、灰色或黑色。算法开始前所有顶点都是白色，随着搜索的进行，各顶点会逐渐变成灰色，然后成为黑色。在搜索中第一次碰到一顶点时，我们说该顶点被发现，此时该顶点变为非白色顶点。因此，灰色和黑色顶点都已被发现，但是，宽度优先搜索算法对它们加以区分以保证搜索以宽度优先的方式执行。若(u,v)E 且顶点 u 为黑色，那么顶点 v要么是灰色，要么是黑色，就是说，所
3、有和黑色顶点邻接的顶点都已被发现。灰色顶点可以与一些白色顶点相邻接，它们代表着已找到和未找到顶点之间的边界。在宽度优先搜索过程中建立了一棵宽度优先树，起始时只包含根节点，即源顶点 s.在扫描已发现顶点 u 的邻接表的过程中每发现一个白色顶点 v，该顶点 v 及边(u,v)就被添加到树中。在宽度优先树中，我们称结点 u 是结点 v 的先辈或父母结点。因为一个结点至多只能被发现一次，因此它最多只能有-个父母结点。相对根结点来说祖先和后裔关系的定义和通常一样：如果 u 处于树中从根 s 到结点 v 的路径中，那么 u 称为 v 的祖先，v 是 u 的后裔。下面的宽度优先搜索过程 BFS 假定输入图
4、G=(V,E)采用邻接表表示，对于图中的每个顶点还采用了几种附加的数据结构，对每个顶点 uV，其色彩存储于变量 coloru中，结点 u 的父母存于变量 u中。如果 u 没有父母 (例如 u=s 或 u 还没有被检索到) ，则 u=NIL，由算法算出的源点 s 和顶点 u 之间的距离存于变量 du中，算法中使用了一个先进先出队列 Q 来存放灰色节点集合。其中 headQ表示队列 Q的队头元素，Enqueue(Q,v)表示将元素 v 入队， Dequeue(Q)表示对头元素出队；Adju表示图中和 u 相邻的节点集合。procedure BFS(G,S);begin1. for 每个节点 uVG
5、-s dobegin2. coloruWhite;3. du;4. uNIL;end;5. colorsGray;6. ds0;7. sNIL;8. Qs9. while Q dobegin10. uheadQ;11. for 每个节点 vAdju do12. if colorv=White thenbegin13. colorvGray; 14. dvdv+1;15. vu;16. Enqueue(Q,v);end; 17. Dequeue(Q);18. coloruBlack;end;end; 图 1 展示了用 BFS 在例图上的搜索过程。黑色边是由 BFS 产生的树枝。每个节点 u 内的
6、值为 du，图中所示的队列 Q 是第 9-18 行 while 循环中每次迭代起始时的队列。队列中每个结点下面是该结点与源结点的距离。图 1 BFS 在一个无向图上的执行过程过程 BFS 按如下方式执行，第 1-4 行置每个结点为白色，置 du为无穷大，每个结点的父母置为NIL，第 5 行置源结点 S 为灰色，即意味着过程开始时源结点已被发现。第 6 行初始化 ds为 0，第 7 行置源结点的父母结点为 NIL，第 8 行初始化队列 0，使其仅含源结点 s，以后 Q 队列中仅包含灰色结点的集合。程序的主循环在 9-18 行中，只要队列 Q 中还有灰色结点，即那些已被发现但还没有完全搜索其邻接表
7、的结点，循环将一直进行下去。第 10 行确定队列头的灰色结点为 u。第 11-16 行的循环考察 u 的邻接表中的每一个顶点 v。如果 v 是白色结点，那么该结点还没有被发现过，算法通过执行第 13-16 行发现该结点。首先它被置为灰色，距离 dv置为 du+1，而后 u 被记为该节点的父母，最后它被放在队列 Q的队尾。当结点 u 的邻接表中的所有结点都被检索后，第 17-18 行使 u 弹出队列并置成黑色。分析在证明宽度优先搜索的各种性质之前，我们先做一些相对简单的工作分析算法在图 G=(V,E)之上的运行时间。在初始化后，再没有任何结点又被置为白色。因此第 12 行的测试保证每个结点至多只
8、能迸人队列一次，因而至多只能弹出队列一次。入队和出队操作需要 O(1)的时间，因此队列操作所占用的全部时间为 O(V)，因为只有当每个顶点将被弹出队列时才会查找其邻接表，因此每个顶点的邻接表至多被扫描一次。因为所有邻接表的长度和为 Q(E)，所以扫描所有邻接表所花费时间至多为 O(E)。初始化操作的开销为 O(V)，因此过程 BFS 的全部运行时间为 O(V+E)，由此可见，宽度优先搜索的运行时间是图的邻接表大小的一个线性函数。最短路径在本部分的开始，我们讲过，对于一个图 G=(V,E)，宽度优先搜索算法可以得到从已知源结点 sV到每个可达结点的距离，我们定义最短路径长度 (s,v)为从顶点
9、s 到顶点 v 的路径中具有最少边数的路径所包含的边数，若从 s 到 v 没有通路则为。具有这一距离 (s,v)的路径即为从 s 到 v 的最短路径（后文我们将把最短路径推广到赋权图，其中每边都有一个实型的权值，一条路径的权是组成该路径所有边的权值之和，目前讨论的图都不是赋权图）。在证明宽度优先搜索计算出的就是最短路径长度之前，我们先看一下最短路径长度的一个重要性质。引理 1设 G=(V,E)是一个有向图或无向图，sV 为 G 的任意一个结点，则对任意边(u,v)E,(s,v)(s,u)+1证明:如果从顶点 s 可达顶点 u，则从 s 也可达 v。在这种情况下从 s 到 v 的最短路径不可能比
10、从 s 到u 的最短路径加上边(u,v)更长，因此不等式成立；如果从 s 不可达顶点 u，则 (s,v)=，不等式仍然成立。我们试图说明对每个顶点 vV，BFS 过程算出的 dv=(s,v)，下面我们首先证明 dv是 (s,v)的上界。引理 2设 G=(V,E)是一个有向或无向图，并假设算法 BFS 从 G 中一已知源结点 sV 开始执行，在执行终止时，对每个顶点 vV，变量 dv的值满足：dv(s,v) 。证明:我们对一个顶点进入队列 Q 的次数进行归纳，我们归纳前假设在所有顶点 vV ，dv(s,v)成立。归纳的基础是 BFS 过程第 8 行当结点 s 被放入队列 Q 后的情形，这时归纳假
11、设成立，因为对于任意结点 vV-s,ds=0=(s,s)且 dv=(s,v)。然后进行归纳，考虑从顶点 u 开始的搜索中发现一白色顶点 v，按归纳假设，du(s,u)。从过程第14 行的赋值语句以及引理 1 可知dv=du+1(s,u)+1(s,v)然后，结点 v 被插入队列 Q 中。它不会再次被插入队列，因为它已被置为灰色，而第 13-16 行的then 子句只对白色结点进行操作，这样 dv的值就不会改变，所以归纳假设成立。为了证明 dv=(s,v)，首先我们必须更精确地展示在 BFS 执行过程中是如何对队列进行操作的，下面一个引理说明无论何时，队列中的结点至多有两个不同的 d 值。引理 3
12、假设 过程 BFS 在图 G=(V,E)之上的执行过程中，队列 Q 包含如下结点，其中 v1 是队列Q 的头，v r 是队列的尾，则 dvidv1+1 且 dvidvi+1, i=1,2,.,r-1。证明:证明过程是对队列操作的次数进行归纳。初始时，队列仅包含顶点 s，引理自然正确。下面进行归纳，我们必须证明在压入和弹出一个顶点后引理仍然成立。如果队列的头 v1 被弹出队列，新的队头为 v2(如果此时队列为空，引理无疑成立)，所以有 dvrdv1+1dv2+1，余下的不等式依然成立，因此 v2 为队头时引理成立。要插入一个结点入队列需仔细分析过程 BFS，在 BFS 的第 16 行，当顶点 v
13、 加入队列成为 vr+1 时，队列头 v1 实际上就是正在扫描其邻接表的顶点 u，因此有 dvr+1=dv=du+1=dv1+1，这时同样有 dvrdv1+1=du+1=dv=dvr+1，余下的不等式 dvrdvr+1仍然成立，因此当结点 v 插入队列时引理同样正确。现在我们可以证明宽度优先搜索算法能够正确地计算出最短路径长度。定理 1 宽度优先搜索的正确性设 G=(V,E)是一个有向图或无向图，并假设 过程 BFS 从 G 上某顶点 sV 开始执行，则在执行过程中，BFS 可以发现源结点 s 可达的每一个结点 vV ，在运行终止时，对任意 vV,dv=(s,v)。此外，对任意从 s 可达的节
14、点 vs，从 s 到 v 的最短路径之一是从 s 到 v的最短路径再加上边(v,v)。证明:我们先证明结点 v 是从 s 不可达的情形。由引理 2，dv(s,v)=，根据过程第 14 行，顶点 v 不可能有一个有限的 dv值，由归纳可知，不可能有满足下列条件的第一个顶点存在：该顶点的 d 值被过程的第 14 行语句置为，因此仅对有有限 d 值的顶点，第 14 行语句才会被执行。所以若 v 是不可达的话，它将不会在搜索中被发现。证明主要是对由 s 可达的顶点来说的。设 Vk 表示和 s 距离为 k 的顶点集合，即 Vk=vV:(s,v)=k 。证明过程为对 k 进行归纳。作为归纳假设，我们假定对
15、于每一个顶点 vV k，在 BFS 的执行中只有某一特定时刻满足： 结点 v 为灰色； dv被置为 k； 如果 vs，则对于某个 uV k-1，v被置为 u； v 被插入队列 Q 中； 正如我们先前所述，至多只有一个特定时刻满足上述条件。归纳的初始情形为 k=0，此时 V0=s，因为显然源结点 s 是唯一和 s 距离为 0 的结点，在初始化过程中，s 被置为灰色，ds 被置为 0，且 s 被放人队列 Q 中，所以归纳假设成立。下面进行归纳，我们须注意除非到算法终止，队列 Q 不为空，而且一旦某结点 u 被插入队列，du和 u都不再改变。根据引理 3 可知如果在算法过程中结点按次序 v1,v2,
16、.,vr 被插入队列，那么相应的距离序列是单调递增的：dv idvi+1，i=1,2,.,r-1 。现在我们考虑任意结点 vV k，k1 。根据单调性和 dvk(由引理 2)和归纳假设，可知如果 v 能够被发现，则必在 Vk-1 中的所有结点进入队列之后。由 (s,v)=k，可知从 s 到 v 有一条具有 k 边的通路，因此必存在某结点 uV k-1，且(u,v)E。不失一般性，设 u 是满足条件的第一个灰色节点( 根据归纳可知集合 Vk-1 中的所有结点都被置为灰色)，BFS把每一个灰色结点放入队列中，这样由第 10 行可知结点 u 最终必然会作为队头出现。当已成为队头时，它的邻接表将被扫描
17、就会发现结点 v（结点 v 不可能在此之前被发现，因为它不与 Vj(jk-1)中的任何结点相邻接，否则 v 不可能属于 Vk，并且根据假定，u 是和 v 相邻接的 Vk-1 中被发现的第一个结点) 。第 13行置 v 为灰色，第 14 行置 dv=du+l=k，第 15 行置 v为 u，第 16 行把 v 插入队列中。由于 v 是 Vk中的任意结点，因此证明归纳假设成立。在结束定理的证明前，我们注意到如果 vV k，则据我们所知可得 vV k-1，这样我们就得到了一条从 s 到 v 的最短路径：即为从 s 到 v的最短路径再通过边 (v,v)。宽度优先树过程 BFS 在搜索图的同时建立了一棵宽
18、度优先树，如 图 1 所示，这棵树是由每个结点的 域所表示。我们正式定义先辈子图如下，对于图 G=(V,E)，源顶点为 s，其先辈子图 G=(V,E)满足：V=vV:vNILs且E=(v,v)E:v V -s如果 V 由从 s 可达的顶点构成，那么先辈子图 G 是一棵宽度优先树，并且对于所有 vV ，G 中唯一的由 s 到 v 的简单路径也同样是 G 中从 s 到 v 的一条最短路径。由于它互相连通，且|E |=|V|-1(由树的性质) ，所以宽度优先树事实上就是一棵树， E 中的边称为树枝。当 BFS 从图 G 的源结点 s 开始执行后，下面的引理说明先辈子图是一棵宽度优先树。引理 4当 过
19、程 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);begin1. if v=s 2. then write(s)3. else if v=nil 4. then writeln(no path from ,s, to ,v, exists.)else begin5. Print_Path(G,s,v);6. write(v);end; end;因为每次递归调用的路径都比前一次调用少一个顶点，所以该过程的运行时间是关于打印路径上顶点数的一个线性函数。
