????????在無權圖中，廣度優先搜索（BFS）是解決最短路徑問題的高效算法。接下來博主從專業角度深入探討其實現細節，并給出C++代碼示例：

---

目錄

一、核心原理

二、算法步驟

三、C++實現關鍵點

1. 數據結構

2. 邊界檢查

3. 路徑回溯（可選）

四、代碼實現

五、路徑回溯實現

六、復雜度分析

七、適用場景與限制

---

一、核心原理

BFS按層遍歷節點，確保首次到達目標節點的路徑是最短的。其核心特性為：

• 隊列管理：先進先出（FIFO）保證按層擴展。

• 訪問標記：避免重復訪問，防止環路。

• 距離記錄：每個節點的距離為父節點距離加1。

---

二、算法步驟

1. 初始化：起點入隊，標記距離為0。

2. 遍歷隊列：逐層處理節點，遍歷所有合法鄰居。

3. 終止條件：到達終點時返回距離；隊列為空則表示不可達。

---

三、C++實現關鍵點

1. 數據結構

• 隊列：存儲待處理節點，使用queue<pair<int, int>>。

• 距離矩陣：記錄每個節點的最短距離，初始化為-1表示未訪問。

• 方向數組：定義移動方向（如4方向或8方向）。

int dx[] = {-1, 1, 0, 0};  // 上下左右
int dy[] = {0, 0, -1, 1};

2. 邊界檢查

確保新坐標在網格范圍內，且節點可訪問（非障礙、未訪問）。

3. 路徑回溯（可選）

通過父節點矩陣記錄路徑，回溯時從終點反向追蹤至起點。

---

四、代碼實現

#include <iostream>
#include <vector>
#include <queue>
using namespace std;int bfsShortestPath(vector<vector<int>>& grid, pair<int, int> start, pair<int, int> end) {int n = grid.size();if (n == 0) return -1;int m = grid[0].size();queue<pair<int, int>> q;vector<vector<int>> dist(n, vector<int>(m, -1));int dx[] = {-1, 1, 0, 0};int dy[] = {0, 0, -1, 1};// 初始化起點q.push(start);dist[start.first][start.second] = 0;while (!q.empty()) {auto curr = q.front();q.pop();// 到達終點if (curr.first == end.first && curr.second == end.second) {return dist[curr.first][curr.second];}// 遍歷四個方向for (int i = 0; i < 4; ++i) {int x = curr.first + dx[i];int y = curr.second + dy[i];// 檢查新坐標是否合法if (x >= 0 && x < n && y >= 0 && y < m && grid[x][y] == 0 && dist[x][y] == -1) {dist[x][y] = dist[curr.first][curr.second] + 1;q.push({x, y});}}}return -1;  // 不可達
}// 示例用法
int main() {vector<vector<int>> grid = {{0, 1, 0, 0},{0, 0, 0, 1},{1, 1, 0, 0},{0, 0, 0, 0}};pair<int, int> start = {0, 0};pair<int, int> end = {3, 3};int shortest = bfsShortestPath(grid, start, end);if (shortest != -1) {cout << "最短路徑長度: " << shortest << endl;} else {cout << "無法到達終點！" << endl;}return 0;
}

---

五、路徑回溯實現

擴展代碼以記錄路徑：

vector<pair<int, int>> getPath(vector<vector<pair<int, int>>>& parent, pair<int, int> start, pair<int, int> end) {vector<pair<int, int>> path;pair<int, int> curr = end;while (curr != start) {path.push_back(curr);curr = parent[curr.first][curr.second];}path.push_back(start);reverse(path.begin(), path.end());return path;
}// 在BFS函數中添加父節點記錄
vector<vector<pair<int, int>>> parent(n, vector<pair<int, int>>(m, {-1, -1}));
// ...
if (條件滿足) {parent[x][y] = curr;
}
// 找到終點后調用getPath

---

六、復雜度分析

• 時間復雜度：O(N×M)，每個節點處理一次。

• 空間復雜度：O(N×M)，隊列和距離矩陣的開銷。

---

七、適用場景與限制

• 適用：無權圖、網格迷宮、社交網絡層級關系。

• 限制：僅處理無權圖，帶權圖需改用Dijkstra或A*算法。

????????通過以上實現，BFS能夠高效解決無權圖中的最短路徑問題。正確管理隊列和狀態標記是保證算法正確性的關鍵。