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