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

1、寬度優(yōu)先搜索寬度優(yōu)先搜索BFSBFS寬度優(yōu)先搜索算法（又稱廣度優(yōu)先搜索）是最簡便的圖的搜索算法之一，這一算法也是很多重要的圖的算法的原型。Dijkstra單源最短路徑算法和Prim最小生成樹算法都采用了和寬度優(yōu)先搜索類似的思想。已知圖G=(VE)和一個源頂點s，寬度優(yōu)先搜索以一種系統(tǒng)的方式探尋G的邊，從而“發(fā)現(xiàn)”s所能到達的所有頂點，并計算s到所有這些頂點的距離(最少邊數(shù))，該算法同時能生成一棵根為s且包括所有可達頂點的寬度優(yōu)先樹。對從

2、s可達的任意頂點v，寬度優(yōu)先樹中從s到v的路徑對應于圖G中從s到v的最短路徑，即包含最小邊數(shù)的路徑。該算法對有向圖和無向圖同樣適用。之所以稱之為寬度優(yōu)先算法，是因為算法自始至終一直通過已找到和末找到頂點之間的邊界向外擴展，就是說，算法首先搜索和s距離為k的所有頂點，然后再去搜索和S距離為kl的其他頂點。為了保持搜索的軌跡，寬度優(yōu)先搜索為每個頂點著色：白色、灰色或黑色。算法開始前所有頂點都是白色，隨著搜索的進行，各頂點會逐漸變成灰色，然后

3、成為黑色。在搜索中第一次碰到一頂點時，我們說該頂點被發(fā)現(xiàn)，此時該頂點變?yōu)榉前咨旤c。因此，灰色和黑色頂點都已被發(fā)現(xiàn)，但是，寬度優(yōu)先搜索算法對它們加以區(qū)分以保證搜索以寬度優(yōu)先的方式執(zhí)行。若(uv)∈E且頂點u為黑色，那么頂點v要么是灰色，要么是黑色，就是說，所有和黑色頂點鄰接的頂點都已被發(fā)現(xiàn)?；疑旤c可以與一些白色頂點相鄰接，它們代表著已找到和未找到頂點之間的邊界。在寬度優(yōu)先搜索過程中建立了一棵寬度優(yōu)先樹，起始時只包含根節(jié)點，即源頂點s.

4、在掃描已發(fā)現(xiàn)頂點u的鄰接表的過程中每發(fā)現(xiàn)一個白色頂點v，該頂點v及邊(uv)就被添加到樹中。在寬度優(yōu)先樹中，我們稱結點u是結點v的先輩或父母結點。因為一個結點至多只能被發(fā)現(xiàn)一次，因此它最多只能有個父母結點。相對根結點來說祖先和后裔關系的定義和通常一樣：如果u處于樹中從根s到結點v的路徑中，那么u稱為v的祖先，v是u的后裔。下面的寬度優(yōu)先搜索過程BFS假定輸入圖G=(VE)采用鄰接表表示，對于圖中的每個頂點還采用了幾種附加的數(shù)據結構，對每

5、個頂點u∈V，其色彩存儲于變量col[u]中，結點u的父母存于變量π[u]中。如果u沒有父母(例如u=s或u還沒有被檢索到)，則π[u]=NIL，由算法算出的源點s和頂點u之間的距離存于變量d[u]中，算法中使用了一個先進先出隊列Q來存放灰色節(jié)點集合。其中head[Q]表示隊列Q的隊頭元素，Enqueue(Qv)表示將元素v入隊，Dequeue(Q)表示對頭元素出隊；Adj[u]表示圖中和u相鄰的節(jié)點集合。procedureBFS(GS