Hướng dẫn giải của Minh họa thuật toán BFS
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhập
Tác giả: Hiếu Nguyễn
, , ,
Editorial for ttbfs: Minh họa thuật toán BFS
Hiểu bài toán
Bài toán yêu cầu thực hiện thuật toán Tìm kiếm theo chiều rộng (BFS) trên một đồ thị vô hướng liên thông. Với mỗi đỉnh, ta duyệt qua các đỉnh kề của nó. Yêu cầu đặc biệt là khi duyệt các đỉnh kề, ta phải ưu tiên thăm các đỉnh có chỉ số nhỏ hơn trước. Đầu vào là n đỉnh và m cạnh, đầu ra là thứ tự các đỉnh được duyệt theo BFS.
Các cách tiếp cận
Cách Sắp xếp hàng xóm trước khi duyệt (Adjacency List + Sort)
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<int> ke[105];
bool visited[105];
void BFS(int start) {
queue<int> q;
q.push(start);
visited[start] = true;
while(!q.empty()) {
int u = q.front();
q.pop();
cout << u << "\n";
// Thu thập các đỉnh chưa thăm
vector<int> next_nodes;
for(int v : ke[u]) {
if(!visited[v]) {
next_nodes.push_back(v);
}
}
// Sắp xếp để ưu tiên đỉnh chỉ số nhỏ
sort(next_nodes.begin(), next_nodes.end());
// Thêm vào hàng đợi và đánh dấu đã thăm
for(int v : next_nodes) {
visited[v] = true;
q.push(v);
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
for(int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
ke[u].push_back(v);
ke[v].push_back(u);
}
// Sắp xếp các danh sách kề ngay từ đầu để đơn giản hóa
for(int i = 1; i <= n; i++) {
sort(ke[i].begin(), ke[i].end());
}
BFS(1);
return 0;
}
- Time Complexity: O(n log n + m) - do sắp xếp các danh sách kề
- Space Complexity: O(n + m) - lưu đồ thị và mảng đánh dấu
Cách tiếp cận này đơn giản và trực quan. Ta xây dựng danh sách kề cho từng đỉnh, sau đó sắp xếp mỗi danh sách kề để các đỉnh hàng xóm có thứ tự tăng dần. Khi thực hiện BFS, ta chỉ cần duyệt tuần tự qua danh sách kề đã được sắp xếp. Tuy nhiên, cách này có thể tốn thời gian sắp xếp nếu đồ thị lớn. Trong code mẫu, ta thấy giải pháp tương tự khi thu thập các đỉnh chưa thăm, sắp xếp và thêm vào hàng đợi.
Cách Sử dụng Priority Queue (Min-Heap)
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<int> ke[105];
bool visited[105];
void BFS_optimized(int start) {
priority_queue<int, vector<int>, greater<int>> pq;
pq.push(start);
visited[start] = true;
while(!pq.empty()) {
int u = pq.top();
pq.pop();
cout << u << "\n";
for(int v : ke[u]) {
if(!visited[v]) {
visited[v] = true;
pq.push(v);
}
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
for(int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
ke[u].push_back(v);
ke[v].push_back(u);
}
BFS_optimized(1);
return 0;
}
- Time Complexity: O((n + m) log n) - do thao tác priority queue
- Space Complexity: O(n + m) - lưu đồ thị và hàng đợi ưu tiên
Thay vì dùng queue thông thường, ta dùng priority_queue (min-heap) để lúc nào cũng lấy ra đỉnh có chỉ số nhỏ nhất. Tuy nhiên, đây không phải là BFS đúng nghĩa mà là biến thể của Dijkstra hoặc Greedy BFS. Ưu điểm là không cần sort lại danh sách hàng xóm, nhưng độ phức tạp tăng lên do log n factor. Cách này thường không tối ưu cho BFS thuần túy nhưng đảm bảo thứ tự ưu tiên.
Cách BFS với mảng đánh dấu và kiểm tra trước khi push
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<int> ke[105];
bool visited[105];
void BFS_standard(int start) {
queue<int> q;
q.push(start);
visited[start] = true;
while(!q.empty()) {
int u = q.front();
q.pop();
cout << u << "\n";
// Danh sách kề phải được sắp xếp sẵn
for(int v : ke[u]) {
if(!visited[v]) {
visited[v] = true;
q.push(v);
}
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
for(int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
ke[u].push_back(v);
ke[v].push_back(u);
}
// Bắt buộc phải sắp xếp tất cả danh sách kề
for(int i = 1; i <= n; i++) {
sort(ke[i].begin(), ke[i].end());
}
BFS_standard(1);
return 0;
}
- Time Complexity: O((n + m) log n) - do sắp xếp các danh sách kề
- Space Complexity: O(n + m)
Đây là phiên bản BFS chuẩn chỉ sau khi đã sắp xếp danh sách kề. Sau khi nhập đồ thị, ta sắp xếp tất cả các vector ke[i]. Khi thực hiện BFS, ta chỉ cần duyệt theo thứ tự trong vector đã sắp xếp và push vào queue nếu chưa thăm. Đây là cách hiệu quả và đúng đắn nhất cho bài toán này.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(n log n + m) - do sắp xếp các danh sách kề | O(n + m) - lưu đồ thị và mảng đánh dấu | Sắp xếp hàng xóm trước khi duyệt (Adjacency List + Sort) |
| 2 | O((n + m) log n) - do thao tác priority queue | O(n + m) - lưu đồ thị và hàng đợi ưu tiên | Sử dụng Priority Queue (Min-Heap) |
| 3 | O((n + m) log n) - do sắp xếp các danh sách kề | O(n + m) | BFS với mảng đánh dấu và kiểm tra trước khi push |
Bài học kinh nghiệm
- BFS truyền thống dùng queue nhưng thứ tự thăm hàng xóm phụ thuộc vào cách ta duyệt danh sách kề
- Để ưu tiên đỉnh chỉ số nhỏ, ta phải đảm bảo duyệt danh sách kề theo thứ tự tăng dần
- Có thể sắp xếp trước danh sách kề hoặc dùng vector phụ để sort trước khi push vào queue
Lỗi thường gặp
- Không sắp xếp danh sách kề dẫn đến thứ tự duyệt không đúng yêu cầu (đỉnh lớn hơn có thể được thăm trước)
- Đánh dấu visited sai thời điểm: nếu đánh dấu khi push vào queue sẽ đảm bảo không bị lặp, nhưng nếu đánh dấu khi pop thì có thể push trùng
- Quên kiểm tra visited trước khi push vào queue导致 duplicate node trong queue
Bình luận