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