<script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script> # Breadth First Search - 廣度優先搜索 -------- #### 問題 在$$ n $$行$$ m $$列的的二維方格圖$$ s = n \times m $$中從$$ beg $$點移動到$$ end $$點。 #### 解法 廣度優先搜索是優先搜索二維方格圖$$ s $$中每個節點的相鄰節點，與之相對的深度優先搜索則會沿著節點的一個相鄰節點試圖走到最遠。 例如在下面這個$$ 5 \times 4 $$二維方格$$ s $$中從$$ beg = [1,0] $$移動到$$ end = [4,3] $$。初始時將起點$$ beg $$加入待搜索節點的隊列$$ queue $$中，之后每次從$$ queue $$中取出頭節點$$ e $$，訪問$$ e $$四周從未被訪問的鄰節點，并將鄰節點加入$$ queue $$中。將每個節點加入$$ queue $$之前將其染為紅色，避免重復訪問。  $$ (1) $$初始時將$$ beg = [1,0] $$染紅并加入$$ queue $$； $$ (2) $$從$$ queue $$中取出頭節點$$ [1,0] $$，因$$ [1,0] \ne end $$，將其四周未被染紅的節點$$ [0,0], [1,1], [2,0] $$染紅并加入$$ queue $$，圖中$$ queue $$的左邊為頭部，右邊為尾部，新訪問的節點插入隊列尾部，每次從隊列中取出頭節點$$ e $$：  $$ (3) $$從$$ queue $$中取出頭節點$$ [0,0] $$，因$$ [0,0] \ne end $$，將其四周未被染紅的節點$$ [0,1] $$染紅并加入$$ queue $$；   $$ \cdots $$  $$ (4) $$從$$ queue $$中取出頭節點$$ [1,3] $$，因$$ [1,3] \ne end $$，其四周的節點都已經被染紅，因此不加入任何新節點；  $$ \cdots $$   $$ (5) $$從$$ queue $$中取出頭節點$$ [4,3] $$，因$$ [4,3] = end $$，算法結束； 本章的圖搜索中，一個節點通常只需要搜索一次，常用染色來標記一個節點是否被搜索過，染紅后就不會再放入待搜索隊列$$ queue $$中。用類似“父節點”指針來記錄搜索時遇到節點的上一個節點，搜索完成時通過“父節點”逆向的找到一條從$$ end $$回到$$ beg $$的路徑。 該算法的時間復雜度為$$ O(n \times m) $$。 -------- #### 源碼 [BreadthFirstSearch.h](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/Search/BreadthFirstSearch.h) [BreadthFirstSearch.cpp](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/Search/BreadthFirstSearch.cpp) #### 測試 [BreadthFirstSearchTest.cpp](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/Search/BreadthFirstSearchTest.cpp)