1.關于BFS的Key_word：

①hash或狀態壓縮記錄狀態? ②狀態剪枝 ③反向BFS ④雙向BFS ⑤特殊初始化VIS數組 ⑥動態圖的搜索 ⑦優先隊列優化搜索 ⑧數位搜索

下面是一一講解：

1.hash或狀態壓縮記錄狀態?：

　　當狀態太多而且邊界也廣時數組難以存儲狀態時或者題目對空間的要求較為苛刻，這時候就要使用狀態壓縮來保存所需的狀態或者hash的方式將一個狀態對應為一個整數通過一維數組來記錄是否訪問，當數據過于離散時可以考慮使用map，但是相應的時間復雜度也會上升，如果真的要將所有狀態限定在一個較小的范圍，可以使用雙hash，不過一般的狀態相對來說不會太難表示，而是考察對于每個搜索狀態的如何設計轉移，有點像DP，誰讓DP搜索不分家。

2.狀態剪枝：

　　沒有剪枝的搜索是沒有靈魂的，無論DFS還是BFS，對于DFS而言我們是一層一層的尋找，當我們知道某一子樹不可能找的結果，或者說這一狀態在具有更有條件時訪問過便不再擴展，但是并不代表著，我小于當前最優解就意味著我的子樹中不存在最優解，這一段的說明見⑦。但是剪枝需要嚴謹的證明過程，盲目的剪枝不可取，要根據題目具體設計在狀態轉移中的剪枝條件，這個在BFS中沒有什么規律可循，每一道題都意味著你需要在題目中發掘隱含條件進行剪枝，例如：當到達同一狀態時，Dis1<Dis2，那么顯而易見，Dis2的后續就要被剪掉，因為在這一點具有同樣的轉移的后續，但是在這一點有最優的選擇，且最優選擇的結果一定好于所有其他選擇，那么進行剪枝，那么會發現只有著明確的相似關系，且有著明顯的先后優劣狀態的狀態需要剪枝，但是在題目中很難找到一眼可以剪枝的關系，這就需要進一步的推導與證明，當這一點學好之后，對于DP的學習會發現，經過各種剪枝的搜索就是DP，不采取遞歸手段訪問每一可能的狀態。

3.反向BFS:

　　例如，在一個迷宮中有N個人，請找出最快走出迷宮的那個人？ 那么我們正向考慮問題，對于N個人那么他們快走出迷宮的話需要求N次BFS，比較步數，那么當N大到一定程度時，爆棧，不需要很大圖就會爆棧，那么反向考慮，我們換種問法，迷宮中有一個人，有N個出口，請問他最快從哪個出口中走出?? ?如果這么問，我們一定會思路泉涌，但是題目絕對不會出這么簡單地變換，我們在改造一下這個問題，有N個人M個出口的題目我們該如何解決，一種解決方法是建圖，Floyd求最短路比較大小時間復雜度為O（(N+M)^3+(N+M)^2）, 我們這里給出BFS的方式，至于時間復雜度只能說隨緣，但是思路何嘗不是一個好思路，我們先比較N和M的大小，通過小的作為搜索起點，那么我們第一次搜索的Dis設置為最優解，第二次搜索時若大于Dis還無解，一定無解，跳出，通過不斷搜索的不斷更新最優解的方式搜索復雜度應該在 O（MIN（N，M）*ans）——O（MIN（N，M）*dis first）之間，那么遍歷圖上的任何點的時間為（N+M）^2，在乘以min（N，M），那么時間復雜度最大是個（N+M）^2*Min(n,m)，對于時間復雜度一定優于第一種，對于其他的方法可以使使用隊列優化的dijkstra，O（（N+M）*Log（N+M）*min(N,M))的復雜度，對于更好的方法現在，我還不太清楚，當然最短路不在我們的討論范圍內，因為有些情況是不能處理的，訪問與后續，所以稍稍改動就只能使用BFS。

4.雙向BFS

?

無論從ans還是從start開始擴展，都以幾何的趨勢增長無論從哪一方開始搜索都會爆棧，但是ans與start之間的路很少，通過雙向搜索找到中間點這種方式絕對會更加快速，圖比較丑也不太形象，但大體的思想還是表現出來。適用于狀態轉移方向太多，但是距離較短的的情況。

5.特殊化的VIS數組

對于一張圖我們vis=1時為訪問，vis=0時為未訪問，第二次用的時候就需要memset，但是時間太長，我們換一種思想，對于vis=n時，為訪問過，vis！=1為未訪問，那么如果vis中的沒有N的話那就不用初始化了，那么對于第一遍之后的vis數組之后1或0，那么我們使n=2，即可不用初始化，第三遍時等于3，以此類推。

6.動態圖的搜索

圖的情況會隨時間軸改變，那么需要在狀態的維度中增加一個時間維度，而且不同時間的狀態不同，同狀態不同時間理解為不同的狀態，那么對于動態圖的搜索，不能簡單vis數組，而是要記錄時間軸，狀態的疊加。

7.優先隊列搜索

對于優先隊列優化的搜索，必須要證明當前的最優解的擴展一定比不是最優解的擴展要優，即當前不是最優未來一定不是最優。不然使用優先隊列優化的搜索必錯。

8.數位搜索

這個搜索雖然寫到這，不是需要注意什么，而是說數位搜索很基礎，不太好像，但是一定能做。更多的是K進制數，用除法求余什么。比如一個500位的數，怎么取模？

想想小學的除法算式怎么寫？ 不是一位一位的除嗎？多少位的也可以做。

總結

以上是生活随笔為你收集整理的图论--BFS总结的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。