BFS Đa Nguồn (Multi-Source BFS)

Xin chào anh em, lại là tôi - Jim đây!

Khi nhắc đến BFS thì khả năng là anh em đã quá quen thuộc với thuật toán duyệt đồ thị này rồi. Vậy thì hôm nay, tôi sẽ chia sẻ với anh em một kỹ thuật cực kỳ mạnh mẽ nhưng lại đơn giản đến bất ngờ liên quan đến thuật toán BFS: Multi-Source BFS.

1. Khi Một Nguồn Là Không Đủ

Tưởng tượng anh em là người đứng đầu trung tâm điều phối cứu hộ của một thành phố. Một thảm họa, ví dụ như đại dịch zombie, vừa bùng phát tại nhiều địa điểm cùng một lúc. Nhiệm vụ của anh em là phải nhanh chóng tính toán cho mỗi người dân, họ cần di chuyển trong thời gian ngắn nhất là bao lâu để đến được một trong những nơi trú ẩn an toàn gần nhất.

Cách tiếp cận đầu tiên, có lẽ là trực quan nhất, là xem xét từng người dân một. Với người A, anh em sẽ chạy thuật toán tìm đường đi ngắn nhất như Breadth-First Search (BFS) để tìm khoảng cách đến từng nơi trú ẩn, sau đó lấy kết quả nhỏ nhất. Lặp lại quy trình này cho tất cả mọi người.

Cách tiếp cận này, mà chúng ta gọi là ngây thơ, có một vấn đề chí mạng: nó quá chậm. Nếu thành phố có V địa điểm và E con đường, có N người dân và S nơi trú ẩn, độ phức tạp tính toán sẽ vào khoảng $O(N * S * (V + E))$. Trong một cuộc thi lập trình với giới hạn thời gian chỉ 1-2 giây, giải pháp này chắc chắn sẽ nhận về thông báo "Time Limit Exceeded".

Vậy, có cách nào để chúng ta phát tín hiệu từ tất cả các nơi trú ẩn cùng một lúc và để tín hiệu tự lan tỏa khắp thành phố không? Câu trả lời là có, và đó chính là vẻ đẹp của Multi-Source BFS (MS-BFS). Đây là một kỹ thuật đơn giản, cho phép chúng ta giải quyết lớp bài toán này với hiệu quả đáng kinh ngạc.

2. Ôn Lại Kiến Thức: BFS Một Nguồn

Để hiểu Multi-Source BFS, trước tiên chúng ta phải nắm vững người anh em của nó: BFS một nguồn (Single-Source BFS).

2.1. Khái niệm cốt lõi

Breadth-First Search (BFS) là một thuật toán duyệt đồ thị theo chiều rộng. Hãy tưởng tượng nó như một vết dầu loang. Bắt đầu từ một điểm duy nhất (nguồn), nó lan ra các đỉnh hàng xóm trực tiếp (level 1), rồi từ đó lại lan tiếp ra hàng xóm của chúng (level 2), và cứ thế cho đến khi không thể lan đi đâu được nữa.

Đặc tính quan trọng nhất của BFS trên đồ thị không có trọng số là: nó luôn tìm ra đường đi ngắn nhất về mặt số lượng cạnh từ một đỉnh nguồn đến tất cả các đỉnh khác. Điều này xảy ra vì nó không bao giờ khám phá một đỉnh ở level k+1 trước khi tất cả các đỉnh ở level k đã được khám phá hết.

2.2. Các thành phần chính

BFS dựa vào hai công cụ chính:

• Hàng đợi (Queue): Một cấu trúc dữ liệu hoạt động theo nguyên tắc "Vào trước - Ra trước" (FIFO). Chính cơ chế này ép buộc thuật toán phải duyệt theo từng level một cách tuần tự.
• Mảng visited hoặc distance: Để theo dõi các đỉnh đã được thăm, tránh xử lý một đỉnh nhiều lần và ngăn thuật toán rơi vào chu trình vô hạn. Thông thường, người ta khởi tạo tất cả khoảng cách là vô cùng, và khoảng cách của đỉnh nguồn là 0.

2.3. Template Code C++ cho Single-Source BFS

Dưới đây là đoạn code C++ mẫu cho bài toán tìm đường đi ngắn nhất từ đỉnh nguồn startNode đến tất cả các đỉnh khác.

#include <bits/stdc++.h>
using namespace std; const int INF = INT_MAX; // Hàm BFS một nguồn
vector<int> singleSourceBfs(int vCount, const vector<vector<int>>& adj, int startNode)
{ // Khởi tạo mảng khoảng cách với giá trị vô cùng vector<int> distance(vCount + 1, INF); // Hàng đợi để xử lý các đỉnh queue<int> q; // Thiết lập cho đỉnh nguồn distance[startNode] = 0; q.push(startNode); // Vòng lặp chính của BFS while (!q.empty()) { int u = q.front(); q.pop(); // Duyệt qua tất cả các đỉnh kề v của u for (int v : adj[u]) { // Nếu v chưa được thăm (khoảng cách vẫn là INF) if (distance[v] == INF) { // Cập nhật khoảng cách và đưa v vào hàng đợi distance[v] = distance[u] + 1; q.push(v); } } } return distance;
}

3. Multi-Source BFS

Bây giờ, chúng ta sẽ thực hiện một bước nhảy trong tư duy. Multi-Source BFS nghe có vẻ phức tạp, nhưng thực chất, nó chỉ là một sự thay đổi nhỏ trong khâu khởi tạo.

3.1. Ý tưởng

Trong BFS một nguồn, chúng ta khởi tạo hàng đợi bằng một đỉnh nguồn duy nhất. Trong Multi-Source BFS, thay đổi duy nhất là: chúng ta duyệt qua tất cả các đỉnh nguồn và đẩy toàn bộ chúng vào hàng đợi ngay từ đầu. Đồng thời, chúng ta thiết lập khoảng cách của tất cả các đỉnh nguồn này bằng 0.

Mọi thứ khác trong thuật toán BFS — vòng lặp while, cách duyệt đỉnh kề, cách cập nhật khoảng cách — đều được giữ nguyên.

3.2. Tại sao nó hoạt động?

Hãy quay lại với phép ẩn dụ "đám cháy lan". Với Multi-Source BFS, ta châm lửa ở tất cả các đỉnh nguồn cùng một lúc. Hãy hình dung nó như một cuộc đua, mỗi nguồn cử ra một vận động viên. Tất cả xuất phát cùng lúc và chạy với tốc độ như nhau.

Bởi vì tất cả các "đám cháy" đều lan tỏa với tốc độ như nhau, một đỉnh u bất kỳ sẽ được "đốt cháy" lần đầu tiên bởi ngọn lửa xuất phát từ nguồn $s_i$ gần nó nhất. Bất kỳ ngọn lửa nào từ một nguồn xa hơn sẽ đến u sau, nhưng tại thời điểm đó, u đã được đánh dấu là đã thăm và sẽ không được xử lý lại. Do đó, khoảng cách được ghi nhận cho mỗi đỉnh u chính là khoảng cách ngắn nhất từ u đến bất kỳ nguồn nào gần nhất.

3.3. So sánh hiệu quả

• Cách ngây thơ: Chạy BFS từ mỗi nguồn trong số S nguồn. Độ phức tạp là $O(S * (V + E))$.
• Multi-Source BFS: Chỉ cần một lần chạy BFS duy nhất. Độ phức tạp là $O(V + E)$.

Sự khác biệt này là cực kỳ đáng kể, quyết định giữa việc pass và fail một bài toán.

3.3. Template Code C++ cho Multi-Source BFS

Chú ý sự thay đổi duy nhất nằm ở khâu khởi tạo.

#include <bits/stdc++.h>
using namespace std; const int INF = INT_MAX; // Hàm BFS nhiều nguồn
vector<int> multiSourceBfs(int vCount, const vector<vector<int>>& adj, const vector<int>& sourceNodes)
{ // Khởi tạo mảng khoảng cách với giá trị vô cùng vector<int> distance(vCount + 1, INF); // Hàng đợi để xử lý các đỉnh queue<int> q; // --- THAY ĐỔI DUY NHẤT NẰM Ở ĐÂY --- // Thiết lập cho TẤT CẢ các đỉnh nguồn for (int startNode : sourceNodes) { if (distance[startNode] == INF) // Đề phòng nguồn trùng lặp { distance[startNode] = 0; q.push(startNode); } } // ------------------------------------ // Vòng lặp chính của BFS vẫn giữ nguyên while (!q.empty()) { int u = q.front(); q.pop(); for (int v : adj[u]) { if (distance[v] == INF) { distance[v] = distance[u] + 1; q.push(v); } } } return distance;
}

4. Thực Chiến

Lý thuyết sẽ trở nên vô nghĩa nếu không được áp dụng. Chúng ta sẽ cùng giải quyết một số bài toán kinh điển.

4.1. Ví dụ 1: Đại Dịch Zombie (Rotting Oranges)

• Input: Một lưới (grid) $m \times n$ với các ô chứa cam tươi (1), cam thối (2), và ô trống (0).
• Yêu cầu: Tìm thời gian tối thiểu để tất cả cam tươi bị lây nhiễm. Nếu có quả cam tươi nào không thể bị lây, trả về -1.
• Phân tích: Đây là bài toán MS-BFS điển hình. Các quả cam thối ban đầu chính là các nguồn. Thời gian lây lan chính là khoảng cách (số level của BFS).

#include <bits/stdc++.h>
using namespace std; class Solution {
public: int orangesRotting(vector<vector<int>>& grid) { if (grid.empty()) return 0; int rows = grid.size(); int cols = grid[0].size(); queue<pair<int, int>> q; int freshOranges = 0; // Bước 1: Tìm tất cả nguồn (cam thối) và đếm cam tươi for (int r = 0; r < rows; ++r) { for (int c = 0; c < cols; ++c) { if (grid[r][c] == 2) q.push({r, c}); else if (grid[r][c] == 1) ++freshOranges; } } if (freshOranges == 0) return 0; int minutes = 0; vector<pair<int, int>> directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; // Bước 2: Chạy Multi-Source BFS theo từng phút while (!q.empty()) { int levelSize = q.size(); bool rottenThisMinute = false; for (int i = 0; i < levelSize; ++i) { pair<int, int> current = q.front(); q.pop(); for (auto& dir : directions) { int nr = current.first + dir.first; int nc = current.second + dir.second; if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 1) { grid[nr][nc] = 2; // Lây nhiễm --freshOranges; q.push({nr, nc}); rottenThisMinute = true; } } } if (rottenThisMinute) ++minutes; } // Bước 3: Kiểm tra kết quả return freshOranges == 0 ? minutes : -1; }
};

Ví dụ 2: Tìm Lối Thoát (01 Matrix)

• Input: Một ma trận nhị phân $m \times n$ chứa các số 0 và 1.
• Yêu cầu: Với mỗi ô, tìm khoảng cách đến ô 0 gần nhất.
• Phân tích: Đây là bài toán tính khoảng cách đến nguồn gần nhất. Tất cả các ô có giá trị 0 chính là các nguồn.

#include <bits/stdc++.h>
using namespace std; class Solution
{
public: vector<vector<int>> updateMatrix(vector<vector<int>>& mat) { int rows = mat.size(); if (rows == 0) return {}; int cols = mat[0].size(); vector<vector<int>> dist(rows, vector<int>(cols, -1)); // -1 để đánh dấu chưa thăm queue<pair<int, int>> q; // Bước 1: Tìm tất cả các nguồn (ô 0) for (int r = 0; r < rows; ++r) { for (int c = 0; c < cols; ++c) { if (mat[r][c] == 0) { q.push({r, c}); dist[r][c] = 0; } } } vector<pair<int, int>> directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; // Bước 2: Chạy Multi-Source BFS while (!q.empty()) { pair<int, int> curr = q.front(); q.pop(); for (auto& dir : directions) { int nr = curr.first + dir.first; int nc = curr.second + dir.second; if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && dist[nr][nc] == -1) { dist[nr][nc] = dist[curr.first][curr.second] + 1; q.push({nr, nc}); } } } return dist; }
};

5. Mở Rộng

Hiểu được vị trí của một thuật toán trong bức tranh lớn giúp chúng ta biết khi nào nên sử dụng công cụ nào.

5.1. Khi nào dùng gì? BFS, MS-BFS, và Dijkstra

Một câu hỏi tự nhiên sẽ nảy sinh: "Nếu đồ thị có trọng số thì sao?". Lúc này, BFS và MS-BFS không còn đảm bảo tìm được đường đi ngắn nhất nữa. Đây là lúc Dijkstra và biến thể đa nguồn của nó tỏa sáng.

Để giải quyết bài toán này trên đồ thị có trọng số dương, chúng ta sử dụng một kỹ thuật thông minh gọi là Siêu Nguồn (Super-Source).

1. Tạo một đỉnh giả mới, gọi là superSource.
2. Nối superSource này đến tất cả các đỉnh nguồn thật bằng các cạnh có trọng số bằng 0.
3. Chạy thuật toán Dijkstra một nguồn thông thường bắt đầu từ superSource.

Khi Dijkstra bắt đầu, nó sẽ xử lý các nguồn thật trước tiên (vì cạnh đến chúng có trọng số 0). Từ đây, thuật toán hoạt động y hệt như việc các nguồn thật cùng lan tỏa, nhưng lần này nó tôn trọng trọng số của các cạnh.

5.2. Một số kỹ thuật khác

• 0-1 BFS: Khi đồ thị có trọng số chỉ là 0 hoặc 1, ta có thể dùng hàng đợi hai đầu (std::deque) để đạt độ phức tạp $O(V+E)$, tối ưu hơn $O(ElogV)$ của Dijkstra. Cạnh 0 đẩy vào đầu, cạnh 1 đẩy vào cuối.
• Ứng dụng nâng cao: MS-BFS có thể dùng trong các kỹ thuật phức tạp hơn như "Chia căn" (SQRT Decomposition) trên truy vấn, giúp tối ưu hóa thời gian tính toán.

6. Tổng Kết

Lý thuyết suông không bằng một dòng code chạy. Dưới đây là danh sách các bài tập đã được chọn lọc để anh em mài giũa kỹ năng.

6.1. Bài tập trên Lưới (Grid)

• Leetcode - 994. Rotting Oranges
• Leetcode - 542. 01 Matrix
• Leetcode - 1162. As Far from Land as Possible (Gợi ý: Coi các ô đất là nguồn và tìm ô nước có khoảng cách lớn nhất).
• Leetcode - 934. Shortest Bridge (Gợi ý: Dùng DFS/BFS để tìm một hòn đảo, coi tất cả ô của đảo đó là nguồn, rồi chạy MS-BFS để tìm hòn đảo thứ hai).

6.2. Bài tập trên Đồ thị tổng quát

• Codeforces - 796D. Police Stations
• Codeforces - 1272E. Nearest Opposite Parity

Multi-Source BFS là một minh chứng tuyệt vời cho thấy trong lập trình, một thay đổi nhỏ trong tư duy có thể dẫn đến một giải pháp hiệu quả hơn rất nhiều. Chúc anh em luyện tập hiệu quả và biến kỹ thuật này thành một công cụ sắc bén trong kho vũ khí của mình. Hẹn gặp lại anh em trong bài viết tiếp theo về 0-1 BFS, see ya~