不同于深度優(yōu)先搜索，廣度優(yōu)先搜索（breadth-first search，簡稱BFS，又稱寬度優(yōu)先搜索）采取的工具是隊列。
我們回顧一下
深度優(yōu)先搜索，可以發(fā)現(xiàn)：
深度優(yōu)先搜索是通過遞歸實現(xiàn)的，其實就相當于在內(nèi)存中開了一個
棧來實現(xiàn)。
而廣度優(yōu)先搜索通過
隊列來實現(xiàn)，其解決問題的大體思路如下：
首先，將代表初始狀態(tài)的節(jié)點放入隊列queue中;
然后，循環(huán)進行以下操作：
從隊列里面推出一個元素u，將通過u能夠聯(lián)系到的且可以優(yōu)化的節(jié)點v推入隊列中
即：
深度優(yōu)先搜索用棧（stack）來實現(xiàn)，整個過程可以想象成一個倒立的樹形：
1、把根節(jié)點壓入棧中。
2、每次從棧中彈出一個元素，搜索所有在它下一級的元素，把這些元素壓入棧中。并把這個元素記為它下一級元素的前驅(qū)。
3、找到所要找的元素時結束程序。
4、如果遍歷整個樹還沒有找到，結束程序。
廣度優(yōu)先搜索使用隊列（queue）來實現(xiàn)，整個過程也可以看做一個倒立的樹形：
1、把根節(jié)點放到隊列的末尾。
2、每次從隊列的頭部取出一個元素，查看這個元素所有的下一級元素，把它們放到隊列的末尾。并把這個元素記為它下一級元素的前驅(qū)。
3、找到所要找的元素時結束程序。
4、如果遍歷整個樹還沒有找到，結束程序。
廣度優(yōu)先搜索可以用來解決很多問題，比如，求最短路的SPFA算法就是用了寬度優(yōu)先搜索的思想。
posted on 2015-03-07 21:14
marchalex 閱讀(240)
評論(0) 編輯 收藏 所屬分類:
java小程序