寬度優(yōu)先搜索 BFS
寬度優(yōu)先搜索算法（又稱廣度優(yōu)先搜索）是最簡便的圖的搜索算法之一，這一算法也是很多重要的圖的算法的原型。Dijkstra單源最短路徑算法和Prim最小生成樹算法都采用了和寬度優(yōu)先搜索類似的思想。
已知圖G=(V,E)和一個(gè)源頂點(diǎn)s，寬度優(yōu)先搜索以一種系統(tǒng)的方式探尋G的邊，從而“發(fā)現(xiàn)”s所能到達(dá)的所有頂點(diǎn)，并計(jì)算s到所有這些頂點(diǎn)的距離(最少邊數(shù))，該算法同時(shí)能生成一棵根為s且包括所有可達(dá)頂點(diǎn)的寬度優(yōu)先樹。對從s可達(dá)的任意頂點(diǎn)v，寬度優(yōu)先樹中從s到v的路徑對應(yīng)于圖G中從s到v的最短路徑，即包含最小邊數(shù)的路徑。該算法對有向圖和無向圖同樣適用。
之所以稱之為寬度優(yōu)先算法，是因?yàn)樗惴ㄗ允贾两K一直通過已找到和末找到頂點(diǎn)之間的邊界向外擴(kuò)展，就是說，算法首先搜索和s距離為k的所有頂點(diǎn)，然后再去搜索和S距離為k+l的其他頂點(diǎn)。
為了保持搜索的軌跡，寬度優(yōu)先搜索為每個(gè)頂點(diǎn)著色：白色、灰色或黑色。算法開始前所有頂點(diǎn)都是白色，隨著搜索的進(jìn)行，各頂點(diǎn)會逐漸變成灰色，然后成為黑色。在搜索中第一次碰到一頂點(diǎn)時(shí)，我們說該頂點(diǎn)被發(fā)現(xiàn)，此時(shí)該頂點(diǎn)變?yōu)榉前咨旤c(diǎn)。因此，灰色和黑色頂點(diǎn)都已被發(fā)現(xiàn)，但是，寬度優(yōu)先搜索算法對它們加以區(qū)分以保證搜索以寬度優(yōu)先的方式執(zhí)行。若(u,v)∈E且頂點(diǎn)u為黑色，那么頂點(diǎn)v要么是灰色，要么是黑色，就是說，所有和黑色頂點(diǎn)鄰接的頂點(diǎn)都已被發(fā)現(xiàn)?；疑旤c(diǎn)可以與一些白色頂點(diǎn)相鄰接，它們代表著已找到和未找到頂點(diǎn)之間的邊界。
在寬度優(yōu)先搜索過程中建立了一棵寬度優(yōu)先樹，起始時(shí)只包含根節(jié)點(diǎn)，即源頂點(diǎn)s.在掃描已發(fā)現(xiàn)頂點(diǎn)u的鄰接表的過程中每發(fā)現(xiàn)一個(gè)白色頂點(diǎn)v，該頂點(diǎn)v及邊(u,v)就被添加到樹中。在寬度優(yōu)先樹中，我們稱結(jié)點(diǎn)u 是結(jié)點(diǎn)v的先輩或父母結(jié)點(diǎn)。因?yàn)橐粋€(gè)結(jié)點(diǎn)至多只能被發(fā)現(xiàn)一次，因此它最多只能有--個(gè)父母結(jié)點(diǎn)。相對根結(jié)點(diǎn)來說祖先和后裔關(guān)系的定義和通常一樣：如果u處于樹中從根s到結(jié)點(diǎn)v的路徑中，那么u稱為v的祖先，v是u的后裔。
下面的寬度優(yōu)先搜索過程BFS假定輸入圖G=(V,E)采用鄰接表表示，對于圖中的每個(gè)頂點(diǎn)還采用了幾種附加的數(shù)據(jù)結(jié)構(gòu)，對每個(gè)頂點(diǎn)u∈V，其色彩存儲于變量color[u]中，結(jié)點(diǎn)u的父母存于變量π[u]中。如果u沒有父母(例如u=s或u還沒有被檢索到)，則 π[u]=NIL，由算法算出的源點(diǎn)s和頂點(diǎn)u之間的距離存于變量d[u]中，算法中使用了一個(gè)先進(jìn)先出隊(duì)列Q來存放灰色節(jié)點(diǎn)集合。其中head[Q]表示隊(duì)列Q的隊(duì)頭元素，Enqueue(Q,v)表示將元素v入隊(duì)， Dequeue(Q)表示對頭元素出隊(duì)；Adj[u]表示圖中和u相鄰的節(jié)點(diǎn)集合。
procedure BFS(G,S);
begin
1. for 每個(gè)節(jié)點(diǎn)u∈V[G]- 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←
9. while Q≠φ do
begin
10. u←head[Q];
11. for 每個(gè)節(jié)點(diǎn)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產(chǎn)生的樹枝。每個(gè)節(jié)點(diǎn)u內(nèi)的值為d[u]，圖中所示的隊(duì)列Q是第9-18行while循環(huán)中每次迭代起始時(shí)的隊(duì)列。隊(duì)列中每個(gè)結(jié)點(diǎn)下面是該結(jié)點(diǎn)與源結(jié)點(diǎn)的距離。
圖1 BFS在一個(gè)無向圖上的執(zhí)行過程
過程BFS按如下方式執(zhí)行，第1-4行置每個(gè)結(jié)點(diǎn)為白色，置d[u]為無窮大，每個(gè)結(jié)點(diǎn)的父母置為NIL，第5行置源結(jié)點(diǎn)S為灰色，即意味著過程開始時(shí)源結(jié)點(diǎn)已被發(fā)現(xiàn)。第6行初始化d[s]為0，第7行置源結(jié)點(diǎn)的父母結(jié)點(diǎn)為NIL，第8行初始化隊(duì)列0，使其僅含源結(jié)點(diǎn)s，以后Q隊(duì)列中僅包含灰色結(jié)點(diǎn)的集合。
程序的主循環(huán)在9-18行中，只要隊(duì)列Q中還有灰色結(jié)點(diǎn)，即那些已被發(fā)現(xiàn)但還沒有完全搜索其鄰接表的結(jié)點(diǎn)，循環(huán)將一直進(jìn)行下去。第10行確定隊(duì)列頭的灰色結(jié)點(diǎn)為u。第11-16行的循環(huán)考察u的鄰接表中的每一個(gè)頂點(diǎn)v。如果v是白色結(jié)點(diǎn)，那么該結(jié)點(diǎn)還沒有被發(fā)現(xiàn)過，算法通過執(zhí)行第13-16行發(fā)現(xiàn)該結(jié)點(diǎn)。首先它被置為灰色，距離d[v]置為d[u]+1，而后u被記為該節(jié)點(diǎn)的父母，最后它被放在隊(duì)列Q的隊(duì)尾。當(dāng)結(jié)點(diǎn)u的鄰接表中的所有結(jié)點(diǎn)都被檢索后，第17 -18行使u彈出隊(duì)列并置成黑色。
分析
在證明寬度優(yōu)先搜索的各種性質(zhì)之前，我們先做一些相對簡單的工作 ——分析算法在圖G=(V,E)之上的運(yùn)行時(shí)間。在初始化后，再沒有任何結(jié)點(diǎn)又被置為白色。因此第12行的測試保證每個(gè)結(jié)點(diǎn)至多只能迸人隊(duì)列一次，因而至多只能彈出隊(duì)列一次。入隊(duì)和出隊(duì)操作需要O(1)的時(shí)間，因此隊(duì)列操作所占用的全部時(shí)間為O(V)，因?yàn)橹挥挟?dāng)每個(gè)頂點(diǎn)將被彈出隊(duì)列時(shí)才會查找其鄰接表，因此每個(gè)頂點(diǎn)的鄰接表至多被掃描一次。因?yàn)樗朽徑颖淼拈L度和為Q(E)，所以掃描所有鄰接表所花費(fèi)時(shí)間至多為O(E)。初始化操作的開銷為O(V)，因此過程BFS的全部運(yùn)行時(shí)間為O(V+E)，由此可見，寬度優(yōu)先搜索的運(yùn)行時(shí)間是圖的鄰接表大小的一個(gè)線性函數(shù)。