概念

廣度優先搜尋通常會與深度優先搜尋放在一起比較，因為它們都是圖的走訪方式。前面有提到深度優先搜尋會找出每一種組合，而廣度優先搜尋可以找出最佳方式。以走迷宮的例子來看，深度優先搜尋會找出每一條從起點到終點的路線，而廣度優先搜尋會找出從起點到終點最快的路線。

總結來說：

• 需要找出有多少種不同的走法或結果時，通常使用深度優先搜尋（DFS）
• 需要找出距離目標最少需要走多少步時，則通常使用廣度優先搜尋（BFS）

實作

前幾天我們已經談到深度優先搜尋是依賴遞迴或堆疊的方式，而廣度優先搜尋則是依賴佇列。為了找到最快的路線，我們需要嘗試每一個方向，然後將座標推進佇列中，這樣佇列中的步數都會遞增，最終在走到終點時必定會是最短的步數。以下是一個簡單的實作範例：

struct node{
    int x,y,dis;
};
int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0},n = 10,m = 10;
int bfs(int start_x,int start_y,int end_x,int end_y){
    vector<vector<bool>> vis(n, vector<bool>(m, false));
    queue<node> q;
    node start;
    start.x = start_x,start.y = start_y,start.dis = 0;
    q.push(start);
    while(!q.empty()){
        node now = q.front();
        q.pop();
        for(int i = 0;i < 4;i++){
            node nxt;
            nxt.x = now.x + dx[i],nxt.y = now.y + dy[i],nxt.dis = now.dis + 1;
            if(nxt.x >= 0 && nxt.x < n && nxt.y >= 0 && nxt.y < m && !vis[nxt.x][nxt.y]){
                vis[nxt.x][nxt.y] = true;
                if(nxt.x == end_x && nxt.y == end_y){
                    return nxt.dis;
                }
                q.push(nxt);
            }
        }
    }
    return -1;
}

當然，BFS還有許多進階應用，例如回朔或狀態轉移，以及處理有權重的最短路徑等問題。不過在這篇文章中，主要聚焦於基本概念和實作

總結

總結來說，本篇文章比較了 BFS 和 DFS 的不同，並提供基本概念和實作範例，也探討了 BFS 在不同領域中的應用，希望大家能更深入地理解 BFS。

預告

明天會提供一些範例題目，供大家練習和參考。這些題目將有助於更好地理解 BFS 的相關應用和實作細節。