0-1 BFS

Wiki › Thuật toán › Thuật toán đồ thị

huunguyen · Last updated 8, Tháng 4, 2026, 16:27

0-1 BFS tìm đường đi ngắn nhất trên đồ thị có trọng số chỉ gồm 0 và 1 trong $O (V + E)$ — nhanh hơn Dijkstra $O ((V + E) \log V)$ nhờ dùng deque thay priority queue.

Ý tưởng

Thay vì priority queue, dùng deque hai đầu:

Cạnh trọng số 0: push_front (ưu tiên cao — như không tốn chi phí).
Cạnh trọng số 1: push_back (ưu tiên thấp hơn).

Điều này đảm bảo deque luôn có thứ tự tăng dần — tương đương Dijkstra nhưng không cần heap.

Cài đặt

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

// Đồ thị trọng số 0/1: adj[u] = {v, w} với w ∈ {0, 1}
vector<int> bfs_01(int src, int n, vector<vector<pair<int,int>>>& adj) {
    vector<int> dist(n, INT_MAX);
    deque<int> dq;
    dist[src] = 0;
    dq.push_back(src);

    while (!dq.empty()) {
        int u = dq.front(); dq.pop_front();
        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                if (w == 0) dq.push_front(v);
                else        dq.push_back(v);
            }
        }
    }
    return dist;
}

Ví dụ 1: Đi qua ô lưới với chi phí 0/1

Cho lưới $N \times M$ , di chuyển sang ô kề: chi phí 0 nếu ô đó trống, chi phí 1 nếu ô đó là chướng ngại (cần phá). Tìm số chướng ngại tối thiểu để đi từ $(0, 0)$ đến $(N - 1, M - 1)$ :

int min_obstacles(vector<vector<int>>& grid) {
    int n = grid.size(), m = grid[0].size();
    vector<vector<int>> dist(n, vector<int>(m, INT_MAX));
    deque<pair<int,int>> dq;
    dist[0][0] = grid[0][0];
    dq.push_back({0, 0});

    int dx[] = {0,0,1,-1}, dy[] = {1,-1,0,0};
    while (!dq.empty()) {
        auto [x, y] = dq.front(); dq.pop_front();
        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d], ny = y + dy[d];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            int nd = dist[x][y] + grid[nx][ny];
            if (nd < dist[nx][ny]) {
                dist[nx][ny] = nd;
                if (grid[nx][ny] == 0) dq.push_front({nx, ny});
                else                   dq.push_back({nx, ny});
            }
        }
    }
    return dist[n-1][m-1];
}

Ví dụ 2: Đổi hướng cạnh với chi phí 1

Cho đồ thị có hướng, đổi chiều một cạnh tốn 1, giữ nguyên tốn 0. Tìm số cạnh cần đổi ít nhất để có đường từ $s$ đến $t$ :

// Với mỗi cạnh u->v (trọng số 0), thêm cạnh ngược v->u (trọng số 1)
// 0-1 BFS trên đồ thị mới
void build(int u, int v, vector<vector<pair<int,int>>>& adj) {
    adj[u].push_back({v, 0});   // đi đúng chiều: miễn phí
    adj[v].push_back({u, 1});   // đi ngược chiều: tốn 1
}

Tổng quát hóa: Deque BFS cho trọng số ${0, k}$

Nếu trọng số chỉ là 0 hoặc $k$ (hằng số), vẫn dùng deque tương tự. Với trọng số ${0, 1, \dots, K}$ nhỏ, dùng Dial's algorithm (bucket queue).

So sánh

Thuật toán	Trọng số	Độ phức tạp
BFS	$= 1$	$O (V + E)$
0-1 BFS	$\in {0, 1}$	$O (V + E)$
Dijkstra	$\geq 0$	$O ((V + E) \log V)$
Bellman-Ford	Bất kỳ	$O (V E)$

Khi nào dùng 0-1 BFS?

Đồ thị/lưới với chi phí di chuyển chỉ là 0 hoặc 1.
Bài "tối thiểu số lần thay đổi/phá/đổi" trên lưới hoặc đồ thị.
Khi Dijkstra đúng nhưng cần nhanh hơn do $N$ lớn.

Bình luận

Không có bình luận tại thời điểm này.