BFS dùng STL cho lập trình thi đấu (Competitive Programming) trong C++

Breadth First Search (BFS) - Duyệt theo chiều rộng: thuật toán thăm tất cả nút của đồ thị. Chọn một nút, thăm tất cả nút kề, rồi tiếp tục với nút kề của chúng.

Ý tưởng cho Competitive Programming

• Dùng std::queue (STL) cho hàng đợi.
• Dùng vector<vector<int>> hoặc vector<int> adj[] cho danh sách kề.
• Mảng visited[] đánh dấu nút đã thăm (tránh chu trình).
• Code ngắn, nhanh, ít bug.

Ví dụ đầu vào/đầu ra

Đồ thị 6 đỉnh (A-F), ma trận kề:
A: B C D
B: A D E
C: A D F
D: A B C E F
E: B D F
F: C D E

Bắt đầu từ B
Output: B A D E C F

Thuật toán BFS

bfs(vertices, start):
    queue q
    visited[] = false
    q.push(start); visited[start] = true
    
    while q not empty:
        u = q.front(); q.pop()
        print u
        for v in adj[u]:
            if not visited[v]:
                visited[v] = true
                q.push(v)
    end
end

Code tối ưu cho CP (C++17)

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m; // n đỉnh, m cạnh
    cin >> n >> m;
    
    vector<vector<int>> adj(n);
    for(int i = 0; i < m; i++) {
        int u, v; cin >> u >> v;
        --u; --v; // Chuyển 1-based -> 0-based
        adj[u].push_back(v);
        adj[v].push_back(u); // Đồ thị vô hướng
    }
    
    int start; cin >> start; --start;
    
    vector<bool> visited(n, false);
    queue<int> q;
    
    visited[start] = true;
    q.push(start);
    
    cout << "BFS Traversal: ";
    while(!q.empty()) {
        int u = q.front(); q.pop();
        cout << u+1 << " "; // Trả về 1-based
        
        for(int v : adj[u]) {
            if(!visited[v]) {
                visited[v] = true;
                q.push(v);
            }
        }
    }
    cout << endl;
    return 0;
}

Kết quả mẫu

Input:
6 7
1 2
1 3
1 4
2 4
2 5
3 4
3 6
2

BFS Traversal: 2 1 4 5 3 6

Mẹo CP quan trọng

• ios::sync_with_stdio(false); cin.tie(nullptr); - Tăng tốc I/O gấp 3-5 lần.
• Dùng vector<int> adj[n] thay vì vector> nếu n biết trước (nhanh hơn).
• Dùng array<bool, MAXN> thay vector (vector là bitset đặc biệt, chậm hơn).
• 0-based indexing nội bộ, convert khi nhập/xuất.

Độ phức tạp

• Thời gian: O(V + E)
• Không gian: O(V)