Đồ thị (Graph) Phần 4: BFS - Thuật toán tìm kiếm theo chiều rộng

BFS – Breadth-First Search hay còn gọi là tìm kiếm theo chiều rộng là một trong những thuật toán cần biết khi nhập môn vào lý thuyết đồ thị. Tư tưởng chính của thuật toán có thể hiểu giống như việc ném hòn đá vào một vũng nước. Khi làm vậy, ta có thể thấy rằng, xung quanh hòn đá sẽ xuất hiện những vòng tròn xuất phát từ vị trí hòn đá và lan rộng ra – giống như việc chúng ta khi xét từ các đỉnh gần đỉnh gốc trước rồi dần dần xét tới những đỉnh xa nó sau.

Mục lục

1. Bài toán 1

Cho đồ thị vô hướng, không có trọng số \(n\) đỉnh, \(m\) cạnh, 2 đỉnh \(S\) và \(T\) lần lượt thể hiện đỉnh bắt đầu và kết thúc của một đường đi.

Yêu cầu: Tìm đường đi ngắn nhất từ \(S\) tới \(T\).

Input:

Dòng đầu tiên chứa 4 số \(n, m, S, T\) \((3 ≤ n, m, S, T ≤ 200).\)

\(m\) dòng sau, mỗi dòng chứa 2 số nguyên dương \(u, v\) cho ta thông tin: giữa 2 đỉnh \(u, v\) tồn tại một cạnh 2 chiều nối giữa chúng

Output:

Dòng đầu tiên ghi quãng đường ngắn nhất từ \(S\) tới \(T\). Nếu không tồn tại phương án đi từ \(S\) tới \(T\), in ra -1.

Nếu dòng đầu ghi giá trị khác -1, dòng thứ 2 ghi hành trình thỏa mãn tìm được: Bắt đầu từ \(S\), tiếp theo là danh sách các đỉnh tồn tại trên đường đi ngắn nhất từ \(S\) tới \(T\), cuối cùng là đỉnh \(T\).

Sample Input:

Sample Output:

2
1 3 5

Giải thích:

Phân tích bài toán:

Nhận xét: DFS không thể kiểm soát được đường đi ngắn nhất giữa 2 đỉnh cho trước do đặc điểm của DFS là tìm kiếm theo chiều sâu. Chính vì vậy, để xử lý bài này, ta cần phải sử dụng thuật toán BFS.
Thật vậy, thuật toán sẽ sử dụng hàng đợi (queue) để ưu tiên tìm kiếm theo chiều rộng, từ các đỉnh gần S tới xa S. Do đó, đường đi tìm được sẽ luôn là đường đi ngắn nhất bắt đầu từ đỉnh S.
Ta có mã giả BFS như sau:

// quy ước:
// push(x): cho đỉnh x vào cuối queue
// front(): giá trị đầu queue
// pop(): xóa phần tử ở đầu queue

void bfs(u):
	đánh dấu tất cả các phần tử trong mảng visited = false
        // tức chưa thăm
	push(u)
	trong khi queue chưa rỗng:
		int qu = front()
		pop()
		for v kề u:
			nếu như v chưa thăm:	
				L[v] = L[u] + 1 
				// do đường đi từ S đến u luôn ngắn nhất, mà theo thuật toán BFS
                                // đây cũng là đường đi ngắn nhất từ S đến v, mà v kề u nên L[v] = L[u] + 1
				push(v) 
				// đưa v vào cuối queue
				đánh dấu v đã thăm

Thứ tự duyệt đỉnh BFS có thể được hình dung như sau:

Queue hiện tại	Queue sau khi lấy (u)	Queue sau khi đẩy vào
1	rỗng	2 3 4
2 3 4	3 4	3 4
3 4	4	4 5
4 5	5	5 6
5 6	6	6
6	rỗng	rỗng

Để truy vết, ta sử dụng kỹ thuật giống như kỹ thuật đã đề cập ở bài DFS

Code mẫu:

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

const int N = 200;

vector<int> adj[N + 1], Path;

bool visited[N + 1];

int n, m, S, T, L[N + 1], trace[N + 1];

void bfs(int s) {
    memset(visited, false, sizeof (visited));
    // gán tất cả phần tử ở mảng visited = false tức là chưa có đỉnh nào được thăm
    queue<int> q;
    q.push(s);
    L[s] = 0;
    // đường đi từ s tới chính nó được cho là 0
    visited[s] = true;
    // đã thăm đỉnh s
    while (q.size()) {
        // trong khi q chưa rỗng
        int u = q.front();
        // u là phần tử ở đầu hàng đợi q
        q.pop();
        // xóa u
        for (auto v : adj[u]) {
            // for v kề u
            if (visited[v] == false) {
                // nếu v chưa thăm
                L[v] = L[u] + 1;
                trace[v] = u;
                // gán trace[v] = u do u là đỉnh được xét liền trước v
                q.push(v);
                // push v vào cuối hàng đợi q
                visited[v] = true;
                // đánh dấu v đã được thăm
            }
        } 
    }
}

void find_path(int t) {
    int x = t;
    while (true) {
        Path.push_back(x);
        if (x == S) {
            break;
        }
        x = trace[x];
    }
    for (int i = Path.size() - 1; i >= 0; i--) {
        cout << Path[i] << " ";
    }
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> m >> S >> T;
    for (int i = 1; i <= m; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        // tức v kề u
        adj[v].push_back(u);
        // tức u kề v
    }
    memset(L, -1, sizeof (L));
    // gán mọi phần tử ở mảng L là -1 tức hiện tại chưa tồn tại đường đi
    bfs(S);
    cout << L[T] << 'n';
    if (L[T] == -1) {
        return 0;
    }
    find_path(T);
    return 0;
}

→ Độ phức tạp thời gian: O(V + E) với V là số đỉnh của đồ thị, E là số cạnh.

2. Bài toán 2

Cho một lưới ô vuông kích thước \(M x N\). Tất cả các ô đều chứa số \(0\). Bạn Hải vô tình làm đổ lọ mực vào lưới làm cho một số ô vuông biến từ \(0\) thành \(1\). Điều này đã vô tình lọt vào tầm mắt của mẹ bạn Hải, và không ngoài dự đoán, mẹ bạn Hải rất tức giận. Cô ấy muốn phạt Hải bằng cách: với mỗi vết mực ở trên lưới, Hải sẽ bị phạt 1 đồng. Một vết mực được định nghĩa là tập hợp các ô chung cạnh được đánh số \(1\).

Yêu cầu: Hỏi mẹ Hải thu được bao nhiêu tiền từ Hải?

Input:

Dòng đầu tiên chứa 2 số nguyên dương \(M, N\) \((5 ≤ M, N ≤ 200)\).
\(M\) dòng tiếp theo mô tả bảng cho trước, mỗi dòng chứa dãy gồm \(N\) số \(0\) hoặc \(1\) được ghi liền nhau.

Output:

Ghi ra số tiền mẹ Hải thu được từ Hải.

Sample Input:

Sample Output:

Phân tích bài toán:

Dễ thấy, mỗi một vết mực chính là một “thành phần liên thông”, và “thành phần liên thông” ở đây được định nghĩa là một tập hợp các ô chung cạnh được đánh số 1. Suy ra, số lần BFS ở các vị trí có giá trị bằng 1 mà chưa được thăm chính là đáp số của bài toán. Nếu tinh ý, bài này hoàn toàn có thể được giải bằng DFS, nhưng ở đây, mình sẽ chỉ đề cập tới cách tiếp cận bằng thuật toán BFS.

Trước hết, để có thể BFS lên lưới ô vuông, thay vì sử dụng vector adj để lưu tọa độ đỉnh kề, ta khai báo như sau:

const int hx[4] = {-1, 0, 0, 1};
const int hy[4] = {0, -1, 1, 0};
                // trái, trên, phải, dưới

Hai mảng \(hx, hy\) có tác dụng: di chuyển tới các ô chung cạnh lần lượt ở các vị trí trái, trên, phải, dưới so với ô đang xét. Phần còn lại, ta sẽ sử dụng kỹ thuật tương tự như bài toán vừa nhắc phía trên và bài toán 2 trong chương DFS để xử lý. Lưu ý: Khi cộng giá trị chỉ số hàng đang xét với \(hx[i]\) và giá trị chỉ số cột đang xét với \(hy[i]\), phải đảm bảo tọa độ nhận được nằm ở trong lưới ô vuông mới được phép BFS.

Code mẫu:

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

const int N = 200;

bool visited[N + 1][N + 1];

int n, m, a[N + 1][N + 1];

const int hx[4] = {-1, 0, 0, 1};
const int hy[4] = {0, -1, 1, 0};
                // trái, trên, phải, dưới
void bfs(int i, int j) {
    queue<pair<int, int>> q; // giá trị đầu của từng pair để lưu chỉ số hàng, giá trị sau lưu chỉ số cột.
    q.push(make_pair(i, j));
    visited[i][j] = true;
    // đã thăm vị trí có tọa độ (i, j)
    while (q.size()) {
        // trong khi q chưa rỗng
        pair<int, int> u = q.front();
        // u là phần tử ở đầu hàng đợi q
        q.pop();
        // xóa u
        for (int i = 0; i < 4; i++) {
            // for các hướng kề u 
            int dx = hx[i] + u.first;
            int dy = hy[i] + u.second;
            // dx, dy chính là tọa độ mới vừa được loang ra từ u
            if (dx < 1 || dx > m || dy < 1 || dy > n) {
                // nếu như tọa độ thu được nằm ở ngoài lưới -> không xét
                continue;
            }
            if (a[dx][dy] == 0 || visited[dx][dy] == true) {
                // nếu giá trị của tọa độ (dx, dy) là 0 hoặc tọa độ này đã thăm -> không xét
                continue;
            }
            q.push(make_pair(dx, dy));
            // đẩy (dx, dy) vào queue để xét tiếp
            visited[dx][dy] = true;
            // đã thăm vị trí có tọa độ (dx, dy)
        } 
    }
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> m >> n;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> a[i][j];
        }
    }
    memset(visited, false, sizeof (visited));
    // gán tất cả phần tử ở mảng visited = false tức là chưa có đỉnh nào được thăm
    int cnt = 0;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (a[i][j] == 1 && visited[i][j] == false) {
                // nếu như tọa độ (i, j) có giá trị bằng 1 và chưa được thăm, ta sẽ bắt đầu BFS ở đây.
                bfs(i, j);
                ++cnt;
            }
        }
    }
    cout << cnt;
    return 0;
}

3. Khi nào sử dụng thuật toán BFS

Bản chất của thuật toán này chính là loang từ các đỉnh từ gần đến xa đỉnh gốc nhất, nên ứng dụng nổi bật nhất của BFS chính là tìm đường đi ngắn nhất không có trọng số hay trọng số 0 – 1.
Bên cạnh đó, một số ứng dụng của BFS là để giải các bài toán liên quan đến: kiểm tra đồ thị 2 phía, xác định thành phần liên thông…

4. Luyện tập

Đây là một số bài tập luyện tập trong sách Competitive Programming Advanced của Code Dream, đăng ký mua ngay để được luyện tập nhiều dạng bài về thuật toán khác, chấm bài online tại http://oj.codedream.edu.vn

ÁP DỤNG GIẢI BÀI PUSHBOX

Phân tích bài toán:

Dễ thấy, số bước đẩy ít nhất ta cần thực hiện chính là tổng quãng đường nhỏ nhất từ đỉnh 1 tới nút của các hộp. Bên cạnh đó, ta cũng có nhận xét là: lịch trình đẩy thỏa mãn dữ kiện đề bài chính là khi ta đưa các hộp gần nút 1 về trước, rồi sau đó đưa các hộp ở xa nút 1 về sau. Để truy vết, ta sẽ ưu tiên sort theo thứ tự L[K[i]] từ nhỏ đến lớn. Nếu như có ít nhất 2 giá trị L[K[i]] bằng nhau, ta sẽ sort theo K[i] theo thứ tự từ nhỏ đến lớn thì mới in ra đáp án có thứ tự từ điển nhỏ nhất được.

Code mẫu:

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

const int N = 10000;

vector<int> adj[N + 1];

bool visited[N + 1];

int n, m, k, L[N + 1], trace[N + 1], K[N + 1];

void bfs(int s = 1) {
    memset(visited, false, sizeof (visited));
    // gán tất cả phần tử ở mảng visited = false tức là chưa có đỉnh nào được thăm
    queue<int> q;
    q.push(s);
    L[s] = 0;
    // đường đi từ s tới chính nó được cho là 0
    visited[s] = true;
    // đã thăm đỉnh s
    while (q.size()) {
        // trong khi q chưa rỗng
        int u = q.front();
        // u là phần tử ở đầu hàng đợi q
        q.pop();
        // xóa u
        for (auto v : adj[u]) {
            // for v kề u
            if (visited[v] == false) {
                // nếu v chưa thăm
                L[v] = L[u] + 1;
                trace[v] = u;
                // gán trace[v] = u do u là đỉnh được xét liền trước v
                q.push(v);
                // push v vào cuối hàng đợi q
                visited[v] = true;
                // đánh dấu v đã được thăm
            }
        } 
    }
}

void find_path(int t) {
    vector<int> Path;
    while (true) {
        Path.push_back(t);
        if (t == 1) {
            break;
        }
        t = trace[t];
    }
    for (int i = 0; i < Path.size() - 1; i++) {
        cout << Path[i] << " " << Path[i + 1] << 'n';
        // 2 đỉnh liền nhau thì luôn tồn tại cung giữa chúng
    }
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> m >> k;
    for (int i = 1; i <= k; i++) {
        cin >> K[i];
    }
    for (int i = 1; i <= m; i++) {
        int u, v; cin >> u >> v;
        adj[v].push_back(u);
        // tức u kề v
    }
    memset(L, -1, sizeof (L));
    // gán mọi phần tử ở mảng L là -1 tức hiện tại chưa tồn tại đường đi
    bfs();
    int res = 0;
    vector<pair<int, int>> box;
    for (int i = 1; i <= k; i++) {
        res += L[K[i]];
    }
    cout << res << 'n';
    for (int i = 1; i <= k; i++) {
        box.push_back(make_pair(L[K[i]], K[i]));
        // lần lượt push_back quãng đường ngắn nhất từ 1 đến K[i] và K[i] vào vector
    }
    sort(box.begin(), box.end());
    // sort theo thứ tự L[K[i]] từ nhỏ đến lớn. Nếu như L[K[i]] bằng nhau, sort theo K[i]
    for (auto x : box) {
        find_path(x.second);
        // lịch trình thỏa mãn là đường đi ngắn nhất từ K[i] về 1
    }
    return 0;
}