最近碰到BFS和DFS的編程題比較多，所以想整理一下相關(guān)算法的基本思想，以便以后使用宛渐。
1.DFS（深度優(yōu)先搜索）
深度優(yōu)先直白講是一種一條道走到黑，撞了南墻再回頭的算法眯搭。所以其整個(gè)搜索空間可以表示為一個(gè)多叉樹窥翩。其可以用遞歸和棧來(lái)分別實(shí)現(xiàn)×巯桑基本思想如下：
1.1 遞歸實(shí)現(xiàn)DFS
function DFS(root){
遞歸出口：搜索到最底部葉節(jié)點(diǎn)
遞歸部分：循環(huán)當(dāng)前可到達(dá)的所有子節(jié)點(diǎn)：
? ? ? ? ? ? ? ? ? ? ? ?循環(huán)內(nèi)部：處理該子節(jié)點(diǎn)寇蚊，調(diào)用DFS(childrenroot)，復(fù)原該子節(jié)點(diǎn)繁扎。}
1.2 棧實(shí)現(xiàn)DFS
使用棧保存未被檢測(cè)的結(jié)點(diǎn)幔荒，結(jié)點(diǎn)按照深度優(yōu)先的次序被訪問并依次被壓入棧中，并以相反的次序出棧進(jìn)行新的檢測(cè)梳玫。
function DFS(root){
初始：root入棧爹梁；
while(棧非空){
出棧一個(gè)結(jié)點(diǎn)，處理該節(jié)點(diǎn)提澎；
把該節(jié)點(diǎn)可到達(dá)的節(jié)點(diǎn)都依次壓入棧中姚垃；
}
}
2.BFS（廣度優(yōu)先搜索）
廣度優(yōu)先的搜索空間也可以表示為一個(gè)多叉樹。其實(shí)現(xiàn)樹結(jié)構(gòu)的逐層遍歷盼忌。BFS可以用隊(duì)列來(lái)實(shí)現(xiàn)积糯〉嗄梗基本思想如下：
2.1 棧實(shí)現(xiàn)DFS
使用棧保存未被檢測(cè)的結(jié)點(diǎn)，結(jié)點(diǎn)按照深度優(yōu)先的次序被訪問并依次被壓入棧中看成，并以相反的次序出棧進(jìn)行新的檢測(cè)君编。
function DFS(root){
初始：root入隊(duì)列。
while(隊(duì)列非空){
出隊(duì)一個(gè)結(jié)點(diǎn)川慌，處理該節(jié)點(diǎn)吃嘿；
把該節(jié)點(diǎn)可到達(dá)的節(jié)點(diǎn)都依次壓入棧中；
}
}
