多源BFS

定義

多源BFS（多源廣度優先搜索）是一種圖遍歷算法，它是標準BFS（廣度優先搜索）的擴展，主要用于解決具有多個起始節點的最短路徑問題。在多源BFS中，不是從單一源點開始搜索整個圖，而是同時從多個源點出發，尋找這些源點到圖中所有其他節點的最短路徑。這種方法特別適用于邊權都為1的情況，如在網格圖中計算點到點的最短曼哈頓距離或歐幾里得距離。

多源BFS通過初始化一個隊列，將所有源節點放入隊列中開始。算法執行標準的BFS過程，但每次從隊列中取出一個節點進行擴展時，會檢查這個節點是否已經被訪問過，以避免重復處理。每個節點的距離是從其最近的源節點測量的，并且維護一個數據結構（如二維數組或字典）來存儲每個節點的最短距離。

運用情況

1. 網格圖中的最短距離：例如，在一個由0和1組成的矩陣中，0表示可以通過的路徑，1表示障礙，多源BFS可以用來找出每個位置到最近的0的距離。
2. 社交網絡中的影響力傳播：在社交網絡中，如果要計算一個人發布的信息經過多個人傳播后能影響到的最遠節點，可以將初始發布者作為多個源點進行多源BFS。
3. 游戲地圖探索：在某些游戲中，玩家可能從多個入口進入迷宮或地圖，多源BFS可以用來快速找到各個入口到所有可到達點的最短路徑。

注意事項

1. 標記已訪問：確保每個節點只被訪問一次，避免循環和重復計算。
2. 初始化源節點的距離：源節點到自身的距離應初始化為0，非源節點的距離可以初始化為無窮大或一個表示未訪問的特殊值。
3. 使用合適的數據結構：為了高效地管理待訪問節點和已訪問節點的信息，選擇適當的數據結構（如隊列、集合、字典等）至關重要。
4. 剪枝：在某些情況下，可以通過剪枝策略提前終止不必要的搜索路徑，以優化性能。

解題思路

1. 初始化：將所有源節點加入隊列，并初始化所有節點的距離（源節點為0，其余為無窮大或特殊值）。
2. 遍歷：執行BFS循環，直到隊列為空。每次循環從隊列頭部取出一個節點，檢查其鄰居節點。
3. 更新距離：對于當前節點的每個未訪問鄰居，計算從源點通過當前節點到達該鄰居的距離，如果這個距離比已知的最短距離更短，則更新該鄰居的距離，并將其加入隊列。
4. 終止條件：當隊列為空時，所有可達節點的最短距離都已被計算。

AcWing 173. 矩陣距離

題目描述

173. 矩陣距離 - AcWing題庫

運行代碼

#include <iostream>
#include <cstring>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 1010;int n, m;
char g[N][N];
PII q[N * N];
int dist[N][N];void bfs()
{int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};int hh = 0, tt = -1;for(int i = 1; i <= n; i ++ )for(int j = 1; j <= m; j ++ )if(g[i][j] == '1'){dist[i][j] = 0;q[++ tt] = {i, j};}while(hh <= tt){PII t = q[hh ++];for(int i  =0; i < 4; i ++ ){int a = t.x + dx[i], b = t.y + dy[i];if(a <= 0 || a > n || b <= 0 || b > m) continue;if(dist[a][b] != -1) continue;dist[a][b] = dist[t.x][t.y] + 1;q[++ tt] = {a, b};}}
}int main()
{memset(dist, -1, sizeof dist);cin >> n >> m;for(int i = 0; i < n; i ++ ) cin >> g[i + 1] + 1;bfs();for(int i = 1; i <= n; i ++ ){for(int j = 1; j <= m; j ++ ) cout << dist[i][j] << ' ';cout << endl;}return 0;
}

代碼思路

1. 數據結構定義與常量設置:
   • 使用PII（pair<int, int>）類型來表示二維網格中的坐標。
   • dx[]和dy[]數組分別存儲了四個基本方向的橫縱坐標增量，用于遍歷鄰居節點。
   • N定義了網格的最大尺寸，這里設為1010。
2. 變量初始化:
   • 讀取網格的行數n和列數m。
   • 通過cin讀取二維字符矩陣g，'1'代表源點，假設其他位置默認為'0'（雖然代碼中未直接處理'0'的情況，但邏輯上是這樣理解的）。
   • 使用memset將距離矩陣dist初始化為-1，表示尚未訪問。
3. 廣度優先搜索（BFS）實現:
   • 遍歷矩陣，將所有值為'1'的點作為起點，其距離設為0，并將它們的坐標存入隊列q。
   • 開始BFS過程：從隊列中取出一個點，檢查它的四個鄰居（上、下、左、右），若鄰居坐標在矩陣范圍內且尚未訪問過（dist[a][b] == -1），則更新鄰居的距離為當前點的距離加1，并將鄰居加入隊列。這一步確保了從所有源點出發，逐步擴展到整個網格，同時計算每個點到最近源點的距離。
4. 結果輸出：遍歷二維數組dist，按照網格的行列順序輸出每個位置的最短距離，每個數字后面跟一個空格，每行結束后換行打印。

改進思路

1. 代碼注釋和文檔：雖然代碼邏輯相對清晰，但增加更多的注釋說明每個主要步驟的作用、邊界條件處理的原因以及算法的核心思想，可以提高代碼的可讀性和可維護性。

2. 異常處理和輸入驗證：在實際應用中，增加對輸入數據的校驗是非常重要的。比如，可以檢查n和m的范圍是否合理，以及輸入矩陣是否符合預期格式，以避免運行時錯誤。

3. 空間優化：雖然本代碼的空間復雜度已經是線性的，但考慮到在極端情況下（如矩陣幾乎全為'1'）隊列q可能會占用大量內存，可以考慮在BFS過程中直接從當前層節點擴展到下一層，而不是將所有節點都存入隊列，這樣可以減少隊列的最大容量需求。

4. 并行化處理：如果面對的是非常大的矩陣，可以考慮使用多線程或多進程并行執行BFS，每個線程負責處理一部分源點或區域，以加速計算過程。但這需要引入線程同步機制來避免數據競爭問題。

5. 使用STL容器：雖然數組在性能上通常有優勢，但考慮到代碼的靈活性和易讀性，可以考慮使用STL容器如vector<vector<int>>來代替二維數組dist和g，特別是當矩陣大小不固定或需要動態調整時。

6. 常量表達式和類型別名：可以進一步利用C++特性，比如將方向數組定義為constexpr以提高效率，或者使用using Grid = vector<vector<char>>;來定義一個類型別名，使得代碼更加現代和清晰。

7. 宏替換為內聯函數或常量：盡管宏定義在本代碼中簡化了訪問pair成員的操作，但使用內聯函數或const變量可以提供更好的類型安全性和調試信息。

改進代碼

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <limits>
using namespace std;// 方向向量，表示上下左右四個方向
constexpr array<pair<int, int>, 4> directions = {{{-1, 0}, {0, 1}, {1, 0}, {0, -1}}};// 使用vector替代數組以支持動態大小和更現代的C++實踐
using Grid = vector<vector<char>>;
using pii = pair<int, int>; // 簡化pair<int, int>的寫法int n, m;
Grid g;
vector<vector<int>> dist;
queue<pii> q;// BFS函數，計算每個點到最近'1'的距離
void bfs() {while (!q.empty()) {auto [cx, cy] = q.front(); q.pop();for (const auto& [dx, dy] : directions) {int nx = cx + dx, ny = cy + dy;if (nx >= 0 && nx < n && ny >= 0 && ny < m && g[nx][ny] != '1' && dist[nx][ny] == -1) {dist[nx][ny] = dist[cx][cy] + 1;q.push({nx, ny});}}}
}int main() {cin >> n >> m;g.resize(n, vector<char>(m));dist.assign(n, vector<int>(m, -1)); // 初始化距離矩陣為-1// 讀取矩陣for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {cin >> g[i][j];// 將所有的'1'點加入隊列，并初始化其距離為0if (g[i][j] == '1') {dist[i][j] = 0;q.push({i, j});}}}bfs(); // 執行BFS// 輸出結果for (const auto& row : dist) {for (int d : row) {cout << (d != -1 ? d : 0) << ' '; // 如果是-1，表示不可達，輸出0}cout << endl;}return 0;
}