寬度優(yōu)先搜索 bfs

1、寬度優(yōu)先搜索寬度優(yōu)先搜索BFSBFS寬度優(yōu)先搜索算法（又稱廣度優(yōu)先搜索）是最簡便的圖的搜索算法之一，這一算法也是很多重要的圖的算法的原型。Dijkstra單源最短路徑算法和Prim最小生成樹算法都采用了和寬度優(yōu)先搜索類似的思想。已知圖G=(VE)和一個(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)先樹。對從

2、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距離為kl的其他頂點(diǎn)。為了保持搜索的軌跡，寬度優(yōu)先搜索為每個(gè)頂點(diǎn)著色：白色、灰色或黑色。算法開始前所有頂點(diǎn)都是白色，隨著搜索的進(jìn)行，各頂點(diǎn)會(huì)逐漸變成灰色，然后

3、成為黑色。在搜索中第一次碰到一頂點(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í)行。若(uv)∈E且頂點(diǎn)u為黑色，那么頂點(diǎn)v要么是灰色，要么是黑色，就是說，所有和黑色頂點(diǎn)鄰接的頂點(diǎn)都已被發(fā)現(xiàn)。灰色頂點(diǎn)可以與一些白色頂點(diǎn)相鄰接，它們代表著已找到和未找到頂點(diǎn)之間的邊界。在寬度優(yōu)先搜索過程中建立了一棵寬度優(yōu)先樹，起始時(shí)只包含根節(jié)點(diǎn)，即源頂點(diǎn)s.

4、在掃描已發(fā)現(xiàn)頂點(diǎn)u的鄰接表的過程中每發(fā)現(xiàn)一個(gè)白色頂點(diǎn)v，該頂點(diǎn)v及邊(uv)就被添加到樹中。在寬度優(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=(VE)采用鄰接表表示，對于圖中的每個(gè)頂點(diǎn)還采用了幾種附加的數(shù)據(jù)結(jié)構(gòu)，對每

5、個(gè)頂點(diǎn)u∈V，其色彩存儲(chǔ)于變量col[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(Qv)表示將元素v入隊(duì)，Dequeue(Q)表示對頭元素出隊(duì)；Adj[u]表示圖中和u相鄰的節(jié)點(diǎn)集合。procedureBFS(GS