先來看一個問題：搜索的核心是什么？
搜索的核心：就是暴力枚舉所有可能！
不會吧弹砚？双仍！這么通俗，這么接地氣桌吃？
高端的食材往往只需要最樸素的烹飪方式朱沃！
這就是搜索問題的核心，算法什么的茅诱，可以看作是對暴力枚舉的輔助逗物。
搜索的常用算法：DFS(深度優(yōu)先) 和 BFS(廣度優(yōu)先)
DFS 和 BFS 是搜索的核心，貫穿始終让簿。
DFS 的概念源自圖論敬察，但搜索中的 DFS 和圖論中的 DFS 有一些區(qū)別：搜索中的 DFS 一般指通過遞歸實現(xiàn)暴力枚舉；如果不使用遞歸尔当，也可使用棧來實現(xiàn)莲祸，但本質(zhì)上是類似的。
DFS：將狀態(tài)空間映射成一張圖椭迎，狀態(tài)就是圖中的節(jié)點(diǎn)锐帜，狀態(tài)之間的聯(lián)系就是圖的邊，然后在這張圖上進(jìn)行深度優(yōu)先遍歷畜号；
BFS：也是先影射成一張圖：只不過遍歷的策略變?yōu)榱藦V度優(yōu)先缴阎，一層層鋪開遍歷而已；
所以 BFS 和 DFS 只是遍歷這個狀態(tài)圖的兩種方式罷了简软，關(guān)鍵在于如何構(gòu)建狀態(tài)圖蛮拔。
注意事項：
本質(zhì)上，對上面所說的圖進(jìn)行遍歷痹升，最終會生成一顆搜索樹建炫。為了避免重復(fù)訪問，需要記錄已訪問過的節(jié)點(diǎn)疼蛾，這些是所有搜索算法的共有特性肛跌，需要牢記。
另外察郁，在樹上遍歷衍慎，不用擔(dān)心是否有環(huán)，因為樹的本質(zhì)是一個簡單無環(huán)圖皮钠，記錄已經(jīng)訪問的節(jié)點(diǎn)是為了減少時間復(fù)雜度稳捆，避免重復(fù)操作。
DFS 算法流程
- 1麦轰、首先將根節(jié)點(diǎn)入stack眷柔；
- 2期虾、從stack取出第一個節(jié)點(diǎn)，判斷是否為target驯嘱；如果找到镶苞，則結(jié)束搜尋并回傳結(jié)果，否則將它的某一個尚未被檢驗的直接子節(jié)點(diǎn)入棧（BFS和DFS的基本區(qū)別就是此處的鞠评，子節(jié)點(diǎn)入棧方式）
- 3茂蚓、重復(fù)步驟 2。
- 4剃幌、如果不存在未檢測過的直接子節(jié)點(diǎn)(某個分支已遍歷完成)聋涨，則將上一級節(jié)點(diǎn)加入stack中，并重復(fù)步驟 2负乡；
- 5牍白、重復(fù)步驟 4；
- 6抖棘、若stack為空茂腥，表示整張圖都檢查過了，即圖中為搜尋到target切省，結(jié)束并回傳false最岗；
注：這里的 stack 可理解為自實現(xiàn)的棧，也可以理解為調(diào)用棧
DFS 遍歷技巧
DFS 常見的有三種方式：前序遍歷朝捆、中序遍歷般渡、后序遍歷；
前中后序芙盘，對應(yīng)的就是樹的 左驯用、根、右 節(jié)點(diǎn)儒老；
如何分辨該使用哪種遍歷方式呢蝴乔，其實并不難，因為大多數(shù)情況下贷盲，搜索過程中淘这，當(dāng)前節(jié)點(diǎn)的結(jié)果都需要依賴其他節(jié)點(diǎn)剥扣，因而誕生了這三種根據(jù)不同順序遍歷的方法巩剖。
比如，當(dāng)前節(jié)點(diǎn)需要依賴其子節(jié)點(diǎn)的計算結(jié)果钠怯，那么就需要考慮佳魔，使用后序遍歷，自底向上晦炊，遍歷了鞠鲜；
反之宁脊，如果當(dāng)前節(jié)點(diǎn)需要依賴其父節(jié)點(diǎn)的信息，那么就需要使用贤姆，前序遍歷榆苞，自頂向下，遍歷了霞捡。
參考下圖坐漏，DFS的深度優(yōu)先遍歷順序是：A-》B-》E；
BFS 算法流程
BFS 也是圖論中算法的一種碧信，不同于 DFS赊琳， BFS 采用的是橫向搜索方式，輔助算法實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)通常采用隊列結(jié)構(gòu)砰碴，而DFS通常使用棧結(jié)構(gòu)(見上面描述)躏筏。
具體來說，我們不斷從隊頭取出狀態(tài)呈枉，然后將此狀態(tài)對應(yīng)的決策產(chǎn)生的所有新狀態(tài)推入隊尾趁尼，重復(fù)以上過程直至隊列為空；
- 1碴卧、首先將根節(jié)點(diǎn)放入隊列中弱卡。
- 2、從隊列中取出第一個節(jié)點(diǎn)住册，并檢驗它是否為目標(biāo)值：如果找到目標(biāo)婶博，則結(jié)束搜索并回傳結(jié)果；否則將它所有尚未檢驗過的直接子節(jié)點(diǎn)加入隊列荧飞。
- 3凡人、若隊列為空，表示整張圖都檢查過了叹阔，即圖中沒有找到目標(biāo)值挠轴。結(jié)束搜索并回傳false。
- 4耳幢、重復(fù)步驟 2岸晦。
參考下圖，BFS的廣度優(yōu)先遍歷睛藻，會在每一層先遍歷自己的同胞節(jié)點(diǎn)：
DFS 和 BFS 的使用區(qū)別
一般情況癣朗，力扣中關(guān)于搜索的題目筑舅，首先考慮DFS痕慢，大部分時候可以解決瓷产；
而BFS一般考慮用來處理最短路徑問題，用一個哈希表 dist 記錄從源點(diǎn)到圖中其他點(diǎn)的距離按摘；
這個 dist 也可以充當(dāng)防止環(huán)產(chǎn)生的功能包券，這是因為第一次到達(dá)一個點(diǎn)后纫谅，再次到達(dá)此點(diǎn)的距離，一定比第一次到達(dá)的路徑大溅固，利用此特點(diǎn)付秕，就可知道是否是第一次訪問了。
DFS 和 BFS 的差異
DFS 和 BFS 都是對題目設(shè)置的狀態(tài)空間進(jìn)行搜索但：
- DFS 在分叉點(diǎn)會任選一條深入進(jìn)入侍郭，即先挑自己的兒子節(jié)點(diǎn)搜索盹牧，遇到終點(diǎn)則返回，再次返回到分叉口(同胞節(jié)點(diǎn))后励幼，嘗試下一個選擇汰寓。基于此苹粟，我們可以在路徑上記錄一些數(shù)據(jù)有滑；
- BFS 在分叉點(diǎn)會選擇將所有同胞節(jié)點(diǎn)的路徑各嘗試一次，因此需要使用隊列來存儲待處理的節(jié)點(diǎn)嵌削，隊列中最多包含兩層元素毛好，且滿足單調(diào)性，即相同層級(同胞節(jié)點(diǎn))的元素在一起苛秕；
村長總結(jié)
總結(jié)一下搜索類題目的的常見解題套路：
- 1肌访、根據(jù)題目要求構(gòu)建狀態(tài)空間（畫圖）；
- 2艇劫、對圖進(jìn)行遍歷（BFS 或者 DFS）吼驶；
- 3、記錄和維護(hù)狀態(tài)（比如 visited 維護(hù)訪問情況店煞， 隊列和棧維護(hù)狀態(tài)的決策方向等）蟹演；
幾個小技巧：
- DFS 通常都是有遞推關(guān)系的，而遞歸關(guān)系就是圖的邊顷蟀；梳理出遞歸關(guān)系后酒请，就明白選擇哪種遍歷方式(前、中鸣个、后序遍歷)羞反，更合理了；
- BFS 由于其單調(diào)性囤萤，因此適合求解最短距離問題昼窗；
- BFS 中用到的隊列，不一定非得是隊列結(jié)構(gòu)阁将，也可以用哈希表替代膏秫，比如村長用PHP刷題右遭，而PHP是沒有隊列這種數(shù)據(jù)結(jié)構(gòu)的做盅，所以都是用數(shù)組類型模擬缤削；
- visitd(記錄已訪問節(jié)點(diǎn)) 和 dist/cost(記錄距離花費(fèi)等) 都可以起到記錄節(jié)點(diǎn)訪問情況的目的，以防止環(huán)的產(chǎn)生吹榴。
亭敢。。图筹。
如果覺得本文對你有那么一丟丟的幫助帅刀，就抬起爪子點(diǎn)個贊吧！
