在學習完圖狀結構的基本概念後，我們今天要來看常見的搜尋演算法 : 廣度優先搜尋(BFS)，或稱作 先廣後深搜尋

什麼是廣度優先搜尋 ?

廣度優先搜尋(Breadth First Search,BFS)以下簡稱BFS，是一種從某一頂點v開始，一層一層向外擴散的走訪，先拜訪v的相鄰節點，再去拜訪下一層的節點
因此搜尋順序會依照與起點的距離由近到遠進行，由於 BFS 需要按照先進先出（FIFO）的順序處理節點，因此通常會搭配 Queue（佇列）來實作

下圖為BFS的走訪順序

BFS 的應用

• 最短路徑問題
• 迷宮問題
  • Number of Islands
  • Flood Fill

拜訪步驟

一、先從頂點開始，將它放入佇列並標記為已拜訪
二、從佇列中取出一個頂點，拜訪它所有尚未拜訪的相鄰頂點
三、這些新的頂點會被放到佇列尾端，等待之後處理
四、重複 二、三 直到佇列為空

1. 先將 1 加入queue
   

2. 把 1 取出，訪問 1，把 2 3放入queue
   

3. 把 2 取出並訪問，把 2 的子節點 4 放入queue
   

4. 把 3 取出並訪問，把 3 的子節點 5 6 放入queue
   

5. 把 4 取出並訪問，4沒有子節點所以繼續
   

剩下兩個以此類推

程式碼

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector<int> graph[7];

bool visited[7];
void BFS(int start){
    queue<int> q;

    // 把起點放入佇列，並標記為已走訪
    q.push(start);
    visited[start] = true;

    while (!q.empty()){
        // 取出佇列最早被加入的節點
        int cur = q.front();
        q.pop();

        // 走訪到這個節點印出來
        cout << cur << " ";

        // 檢查當前節點 cur 的所有鄰居
        for (int next : graph[cur]){
            if (!visited[next]){
                visited[next] = true; 
                q.push(next); // 加入佇列，等待之後被處理
            }
        }
    }
}

int main(){
    // 建立圖的邊(這裡是無向圖，所以每條邊都要雙向都加)

    graph[1].push_back(2);
    graph[2].push_back(1);  // 反向也要加，這樣才能從 2 走回 1

    graph[1].push_back(3);
    graph[3].push_back(1); 

    graph[2].push_back(4);
    graph[4].push_back(2);  

    graph[3].push_back(5);
    graph[5].push_back(3);  

    graph[3].push_back(6);
    graph[6].push_back(3);  
    
    // 因為是無向圖，理論上從任何一個節點開始都能走訪到全部節點
    cout << "BFS 走訪順序:";
    BFS(1);
    cout << endl;
}

輸出 :

BFS 走訪順序:1 2 3 4 5 6

複雜度

下一篇要介紹另一種走訪方式 : DFS(深度優先搜尋)，會呼應到我們更早之前學過的堆疊，敬請期待~~
21天了繼續加油~~

參考資料和書籍

1. https://zh.wikipedia.org/zh-tw/%E5%B9%BF%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2#%E5%B0%8B%E6%89%BE%E9%80%A3%E6%8E%A5%E5%85%83%E4%BB%B6
2. https://www.raind.blog/c&cpp-zh/c&cpp_bfs