BFS 廣度優先搜尋– 陪你刷題

當要尋找兩點間最短距離時，就可以應用BFS ，本質上就是將題目的起點、終點與所有可能性放到圖中，找尋起點與終點間最短距離。

另外一種常見的應用則是 ... 跳至主要內容Leetcode邁向千題的關卡，想要把所有題目刷過一遍，對於一位上班族來說就跟寫出來的程式沒有bug一樣困難，因此想要將刷題常用的觀念技巧與其對應題目整理出來，一方面可以整理自己思緒，也可以做為未來複習用。

這系列文章會一直持續下去，算是作為工程師職涯的隨身裝備。

何時使用BFS當要尋找兩點間最短距離時，就可以應用BFS，本質上就是將題目的起點、終點與所有可能性放到圖中，找尋起點與終點間最短距離。

另外一種常見的應用則是Tree的levelordertraversal。

相對於DFS，BFS更適合用來解決找最短距離的問題，其代價則是有較大的空間複雜度。

BFS操作框架典型的BFS需要以下三種資料結構：透過queue的FIFO特性來紀錄走訪過且待處理的vertex(頂點)。

用visited陣列來記錄各vertex是否被走訪過，避免vertex被重複訪問。

如果圖是binarytree，就不會有重複造訪的情況，就不需要visited如果vertex不是由固定範圍的integer所構成，那就用unordered_set來紀錄vertex是否走訪過（以C++來說）用prev來紀錄搜尋路徑。

prev[s]=t，代表由t走到s，也就是說prev[s]表示頂點s是由哪個頂點走過來的。

BFS操作順序如下，可以搭配下面的示意圖與程式碼來理解：把起點放到queue裡，並將其在visited陣列中對應值寫成1表示拜訪過。

從queue的前端拿出vertex(最早放入的，queue的FIFO特性）。

檢查拿出的vertex的所有鄰近vertices中，將尚未走訪過的放進queue中，並執行以下動作：將其在visited陣列中對應值寫成1將其在prev陣列中對應值寫成拿出的vertex移除queue前端的vertex。

不斷重複步驟2~4直到queue為空。

最終可以由prev陣列構建出BFS的走訪順序。

intBFS(intstart,inttarget) { queuequ; intshortest_step=0; intvisited[size]={0}; intprev[size]={-1}; qu.push(start); while(!qu.empty()) { intround=q.size(); for(inti=0;i>levelOrder(TreeNode*root){ vector>result; queueq; if(root!=nullptr) q.push(root); while(!q.empty()) { intqu_size=q.size(); vectorlevel_vec; for(inti=0;ival); if(top_node->left!=nullptr) { q.push(top_node->left); } if(top_node->right!=nullptr) { q.push(top_node->right); } q.pop(); } result.push_back(level_vec); } returnresult; }延伸練習#111,#199Leetcode#127WordLadder這題要從一個單字，每次只能改變一個字元，問你最少轉換幾次才可以轉換到目標單字。

看到找最少次數，就可以想到BFS。

可以想像所有單字都是圖中的vertex，從起始單字開始，走到目標單字的最短路徑是我們要的答案，接下來思考中會碰到一個問題，這張圖中究竟有多少點，這些點是怎麼連接的呢？以h-i-t這個單字來說，總共包含3個字元，每個字元都可以轉換為另外26個字母，轉換後的結果必須在wordList內，才能出現在圖上。

每轉換出一個新單字，需要做下列檢查：替換的字元不能跟未替換前一樣替換後如果是目標，直接回傳結果如果出現在visited內，直接忽略確認是否屬於wordList內的單字，不屬於裏面的單字不需要處理優化對於上述檢查第3點與第4點，還有值得優化之處。

在執行第3點檢查時，如果wordList內含許多單字狀況下，會遇到TimeLimitExceeded的狀況，等於每替換一次字元，就要把整個wordList掃過一輪去檢查替換後的單字是否在wordList內，時間複雜度太高。

更好的辦法是將wordList換成unordered_set來存放，透過unoredered_set.count()確認單字是否在wordList內，其時間複雜度僅O(1)。

這題有另外一個特別之處在於，可能出現在圖上的節點都被限定於題目給的wordList之中，每次遇到新節點，除了要檢查是不是已經走訪過，還要確定是否有出現在wordList中。

這邊可以做一個優化，將這兩項檢查做結合，每當轉變出一個新的單字，優先檢查該單字是否在wordList中，如果是就將該單字從wordList移除，這樣就可以保證不會再走訪到重複的單字了。

//將wordList轉換為unordered_set unordered_setword_list(wordList.begin(),wordList.end()); //每當有一個新的單字curr，先檢查word_list內是否有這個單字 if(word_list.count(curr)) { qu.push(curr); //走訪過的單字由word_list中移除，避免重複走訪 word_list.erase(curr); }這題完整的程式碼如下：classSolution{ public: intladderLength(stringbeginWord,stringendWord, vector&wordList) { unordered_setpath(wordList.begin(), wordList.end()); if(path.find(endWord)==path.end()) return0; queuequ; qu.push(beginWord); intstep=0; while(!qu.empty()) { step++; inttodo=qu.size(); for(inti=0;i