廣搜的使用場景

廣搜的搜索方式就適合于解決兩個點之間的最短路徑問題。

因為廣搜是從起點出發，以起始點為中心一圈一圈進行搜索，一旦遇到終點，記錄之前走過的節點就是一條最短路。

當然，也有一些問題是廣搜 和 深搜都可以解決的，例如島嶼問題，這類問題的特征就是不涉及具體的遍歷方式，只要能把相鄰且相同屬性的節點標記上就行。 （我們會在具體題目講解中詳細來說）

比如下面這個圖，從start開始慢慢向外擴展，第4次擴展才到end，那么最短路徑的長度就是4，

一旦遇到終止點，那么一定是一條最短路徑。

BFS模板

針對這個圖，有下面的BFS模塊，目的是遍歷整個二維網格，并且記錄哪些位置已經被訪問過。

/*
廣度優先搜索的模板，也就是bfs函數。
*/#include <iostream>
#include <queue>
#include <vector>
using namespace std;// 定義四個可能的移動方向
int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1};
/*** 使用廣度優先搜索（BFS）遍歷二維網格* @param grid 二維網格，通常表示為二維數組* @param visited 記錄網格中各位置是否已被訪問過的二維布爾數組* @param x 起始位置的x坐標* @param y 起始位置的y坐標* 此函數的目的是通過BFS算法遍歷網格中所有連接的位置*/
void bfs(vector<vector<int>> &grid, vector<vector<bool>> &visited, int x, int y)
{// 使用隊列來實現BFS算法queue<pair<int, int>> que;// 將起始位置(x, y)加入隊列，并標記為已訪問que.push({x, y});visited[x][y] = true;// 當隊列不為空時，循環繼續while (!que.empty()){// 獲取隊列頭部的位置pair<int, int> cur = que.front();que.pop();int curx = cur.first;int cury = cur.second;// 遍歷四個可能的移動方向for (int i = 0; i < 4; i++){// 計算下一個位置的坐標int nextx = curx + dir[i][0];int nexty = cury + dir[i][1];// 如果下一個位置超出網格邊界，則跳過if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size())continue;// 如果下一個位置未被訪問過，則加入隊列并標記為已訪問if (!visited[nextx][nexty]){que.push({nextx, nexty});visited[nextx][nexty] = true;}}}
}

算法從起始位置 (x, y) 開始，探索四個相鄰的方向，并訪問所有與起始位置連通的區域。使用隊列來管理待訪問的位置，并且使用 visited 數組來防止重復訪問。

BFS的應用問題

• 迷宮問題：BFS 可以用于尋找迷宮的最短路徑，或者探索從起始點出發，能到達的所有位置。

• 圖的遍歷：BFS 廣泛應用于圖的遍歷中，特別是無權圖中尋找最短路徑時。

• 搜索問題：可以在很多搜索問題中使用 BFS，如路徑規劃、連通區域的計算等。