Bài 18.3. Thuật toán BFS và Ứng dụng

Chào mừng các bạn quay trở lại với chuỗi bài viết về Cấu trúc dữ liệu và Giải thuật! Trong các bài trước, chúng ta đã tìm hiểu về các cấu trúc dữ liệu cơ bản và bắt đầu làm quen với đồ thị - một cấu trúc mạnh mẽ mô hình hóa các mối quan hệ phức tạp. Hôm nay, chúng ta sẽ khám phá một trong những thuật toán kinh điển nhất trên đồ thị: Thuật toán tìm kiếm theo chiều rộng (Breadth-First Search - BFS).

Nếu bạn đã từng nghĩ về cách Google Maps tìm đường đi ngắn nhất, hay cách các mạng xã hội như Facebook kết nối mọi người, hoặc thậm chí là cách giải các bài toán mê cung, thì khả năng cao là bạn đã chạm trán với ý tưởng cốt lõi của BFS rồi đấy!

BFS là gì? Một cái nhìn tổng quan

BFS là một thuật toán dùng để duyệt (hay tìm kiếm) các đỉnh (node) trong một đồ thị (graph) hoặc cây (tree). Điểm đặc biệt của BFS là nó khám phá các đỉnh theo từng "lớp" hay từng "chiều rộng". Bắt đầu từ một đỉnh nguồn, BFS sẽ thăm tất cả các đỉnh kề với đỉnh nguồn, sau đó thăm tất cả các đỉnh kề với các đỉnh vừa được thăm (mà chưa được thăm), và cứ tiếp tục như vậy cho đến khi tất cả các đỉnh có thể truy cập được từ đỉnh nguồn đều đã được thăm.

Hãy tưởng tượng bạn thả một viên đá xuống mặt hồ. Các gợn sóng lan ra từ tâm theo từng vòng tròn đồng tâm. BFS hoạt động tương tự như vậy trên đồ thị: nó lan truyền sự "thăm dò" từ đỉnh nguồn ra các đỉnh "gần hơn" trước, rồi mới đến các đỉnh "xa hơn".

Ngược lại với BFS là DFS (Depth-First Search - Tìm kiếm theo chiều sâu), thuật toán này sẽ đi "sâu" nhất có thể theo một nhánh trước khi quay lại và khám phá các nhánh khác. Sự khác biệt trong cách tiếp cận này dẫn đến những ứng dụng và tính chất khác nhau giữa hai thuật toán.

Cách BFS hoạt động: Sử dụng Queue là Chìa khóa!

Làm thế nào để BFS đảm bảo việc thăm dò theo từng lớp? Bí mật nằm ở cấu trúc dữ liệu Queue (hàng đợi). Queue hoạt động theo nguyên tắc FIFO (First-In, First-Out): phần tử nào vào trước thì ra trước. Đây chính xác là thứ chúng ta cần để xử lý các đỉnh theo thứ tự "gần" đỉnh nguồn nhất trước.

Các bước hoạt động chi tiết của BFS như sau:

Khởi tạo:
- Chọn một đỉnh bất kỳ làm đỉnh bắt đầu (gọi là start_node).
- Tạo một Queue và thêm start_node vào đó.
- Tạo một tập hợp (hoặc mảng boolean) để theo dõi các đỉnh đã được thăm (visited). Đánh dấu start_node là đã thăm.
Duyệt:
- Trong khi Queue chưa rỗng:
  - Lấy (và loại bỏ) một đỉnh u từ đầu Queue (thao tác dequeue).
  - Xử lý đỉnh u (ví dụ: in tên đỉnh, kiểm tra xem nó có phải là đỉnh đích không...).
  - Duyệt qua tất cả các đỉnh v là hàng xóm (neighbor) của đỉnh u.
  - Đối với mỗi hàng xóm v:
    - Nếu v chưa được thăm:
      - Đánh dấu v là đã thăm.
      - Thêm v vào cuối Queue (thao tác enqueue).
Kết thúc: Quá trình dừng lại khi Queue rỗng, nghĩa là tất cả các đỉnh có thể truy cập được từ start_node đã được thăm. Nếu đồ thị có nhiều thành phần liên thông (các phần không kết nối với nhau), bạn có thể cần lặp lại BFS từ một đỉnh chưa thăm bất kỳ để duyệt hết toàn bộ đồ thị.

Tại sao lại dùng Queue? Khi bạn dequeue một đỉnh u, bạn đang lấy ra một đỉnh thuộc "lớp" hiện tại. Khi bạn enqueue các hàng xóm chưa thăm của u, bạn đang thêm chúng vào "lớp" tiếp theo, sau tất cả các đỉnh còn lại trong "lớp" hiện tại. Queue đảm bảo rằng bạn sẽ xử lý hết các đỉnh ở khoảng cách k so với nguồn trước khi xử lý bất kỳ đỉnh nào ở khoảng cách k+1.

Ví dụ Minh Họa Bước Đi Của BFS

Hãy xét một đồ thị đơn giản sau:

Đỉnh: A, B, C, D, E, F Cạnh: (A, B), (A, C), (B, D), (B, E), (C, F)

Bắt đầu BFS từ đỉnh A:

Khởi tạo:
- Start node: A
- Queue: [A]
- Visited: {A}
Bước 1:
- Dequeue: A. Xử lý A (ví dụ: in ra A).
- Hàng xóm của A: B, C.
- B chưa thăm: Đánh dấu B thăm, enqueue B. Visited: {A, B}. Queue: [B].
- C chưa thăm: Đánh dấu C thăm, enqueue C. Visited: {A, B, C}. Queue: [B, C].
Bước 2:
- Dequeue: B. Xử lý B (in B).
- Hàng xóm của B: A, D, E.
- A đã thăm: bỏ qua.
- D chưa thăm: Đánh dấu D thăm, enqueue D. Visited: {A, B, C, D}. Queue: [C, D].
- E chưa thăm: Đánh dấu E thăm, enqueue E. Visited: {A, B, C, D, E}. Queue: [C, D, E].
Bước 3:
- Dequeue: C. Xử lý C (in C).
- Hàng xóm của C: A, F.
- A đã thăm: bỏ qua.
- F chưa thăm: Đánh dấu F thăm, enqueue F. Visited: {A, B, C, D, E, F}. Queue: [D, E, F].
Bước 4:
- Dequeue: D. Xử lý D (in D).
- Hàng xóm của D: B. B đã thăm: bỏ qua. Queue: [E, F].
Bước 5:
- Dequeue: E. Xử lý E (in E).
- Hàng xóm của E: B. B đã thăm: bỏ qua. Queue: [F].
Bước 6:
- Dequeue: F. Xử lý F (in F).
- Hàng xóm của F: C. C đã thăm: bỏ qua. Queue: [].
Kết thúc: Queue rỗng. Quá trình BFS hoàn tất.

Thứ tự các đỉnh được xử lý (in ra) là: A, B, C, D, E, F. Đây là một thứ tự duyệt theo chiều rộng!

Triển Khai BFS Cơ Bản bằng C++

Để triển khai BFS, chúng ta cần biểu diễn đồ thị. Một cách phổ biến và hiệu quả là sử dụng danh sách kề (adjacency list). Với $V$ đỉnh và $E$ cạnh, danh sách kề là một mảng (hoặc vector) có kích thước $V$, trong đó mỗi phần tử là một danh sách (hoặc vector) chứa các đỉnh kề với đỉnh tương ứng.

#include <iostream> // Dành cho cout, cin
#include <vector>   // Dành cho vector (danh sách kề và mảng visited)
#include <queue>    // Dành cho queue (hàng đợi BFS)
#include <list>     // Có thể dùng list cho danh sách kề, nhưng vector<vector<int>> phổ biến hơn

// Hàm thực hiện thuật toán BFS trên đồ thị
void bfs(const std::vector<std::vector<int>>& adj, int start_node) {
    // adj: Danh sách kề biểu diễn đồ thị.
    //      adj[i] là vector chứa các đỉnh kề với đỉnh i.
    // start_node: Đỉnh bắt đầu quá trình BFS.

    int num_vertices = adj.size(); // Số lượng đỉnh trong đồ thị

    // 1. Tạo mảng để đánh dấu các đỉnh đã thăm.
    //    Ban đầu, tất cả các đỉnh đều chưa được thăm.
    //    Kích thước bằng số lượng đỉnh, khởi tạo tất cả là false.
    std::vector<bool> visited(num_vertices, false);

    // 2. Tạo Queue cho BFS.
    std::queue<int> q;

    // 3. Bắt đầu từ đỉnh start_node.
    //    Đánh dấu đỉnh start_node là đã thăm và thêm vào Queue.
    visited[start_node] = true;
    q.push(start_node);

    std::cout << "Thu tu duyet BFS (tu dinh " << start_node << "): ";

    // 4. Duyệt cho đến khi Queue rỗng
    while (!q.empty()) {
        // Lấy đỉnh ở đầu Queue và loại bỏ nó
        int u = q.front();
        q.pop();

        // Xử lý đỉnh u (trong ví dụ này là in ra đỉnh đó)
        std::cout << u << " ";

        // Duyệt qua tất cả các hàng xóm của đỉnh u
        // adj[u] chứa danh sách các đỉnh kề với u.
        for (int v : adj[u]) {
            // Nếu hàng xóm v chưa được thăm
            if (!visited[v]) {
                // Đánh dấu v là đã thăm
                visited[v] = true;
                // Thêm v vào cuối Queue
                q.push(v);
            }
        }
    }
    std::cout << std::endl;
}

int main() {
    // Ví dụ đồ thị (số đỉnh = 5)
    // Các đỉnh được đánh số từ 0 đến 4.
    // adj[i] là danh sách các đỉnh kề với đỉnh i.
    // Ví dụ: Đỉnh 0 kề với 1 và 2.
    //         Đỉnh 1 kề với 0, 3 và 4.
    //         ...
    std::vector<std::vector<int>> adj(5);

    // Thêm các cạnh vào đồ thị (vô hướng)
    // Cạnh (u, v) => thêm v vào danh sách kề của u và thêm u vào danh sách kề của v
    adj[0].push_back(1);
    adj[0].push_back(2);

    adj[1].push_back(0);
    adj[1].push_back(3);
    adj[1].push_back(4);

    adj[2].push_back(0);
    adj[2].push_back(4);

    adj[3].push_back(1);

    adj[4].push_back(1);
    adj[4].push_back(2);

    // Thực hiện BFS bắt đầu từ đỉnh 0
    bfs(adj, 0);

    // Lưu ý: Nếu đồ thị có nhiều thành phần liên thông,
    // hàm bfs(adj, 0) chỉ duyệt được thành phần chứa đỉnh 0.
    // Để duyệt hết toàn bộ đồ thị, bạn cần kiểm tra các đỉnh chưa thăm
    // sau khi một lần BFS kết thúc và chạy BFS lại từ đỉnh chưa thăm đó.
    // Ví dụ:
    /*
    int num_vertices = adj.size();
    std::vector<bool> total_visited(num_vertices, false); // Mảng theo dõi toàn bộ
    for (int i = 0; i < num_vertices; ++i) {
        if (!total_visited[i]) {
            // Gọi hàm BFS mở rộng hơn để cập nhật total_visited
            // và duyệt thành phần liên thông mới.
            // (Cần sửa đổi hàm bfs hoặc viết hàm mới)
        }
    }
    */


    return 0;
}

Giải thích Code:

#include <iostream>, <vector>, <queue>: Bao gồm các thư viện cần thiết cho input/output, sử dụng std::vector cho danh sách kề và mảng visited, và std::queue cho hàng đợi BFS.
std::vector<std::vector<int>> adj: Biểu diễn đồ thị bằng danh sách kề. adj[i] là một vector chứa các chỉ số của các đỉnh kề với đỉnh i. Các đỉnh được đánh số từ 0 đến num_vertices - 1.
std::vector<bool> visited(num_vertices, false): Một vector boolean để ghi nhớ xem một đỉnh đã được thăm trong quá trình BFS chưa. Ban đầu tất cả là false.
std::queue<int> q: Hàng đợi chứa các đỉnh cần được xử lý.
visited[start_node] = true; q.push(start_node);: Đánh dấu đỉnh bắt đầu đã thăm và đưa nó vào hàng đợi.
while (!q.empty()): Vòng lặp chính của BFS. Nó chạy cho đến khi không còn đỉnh nào trong hàng đợi.
int u = q.front(); q.pop();: Lấy đỉnh ở đầu hàng đợi (q.front()) và sau đó loại bỏ nó (q.pop()). Đỉnh u này chính là đỉnh đang được xử lý.
std::cout << u << " ";: Trong ví dụ đơn giản này, việc "xử lý" đỉnh chỉ là in ra chỉ số của nó.
for (int v : adj[u]): Duyệt qua tất cả các hàng xóm v của đỉnh u bằng cách lặp qua danh sách kề adj[u].
if (!visited[v]): Kiểm tra xem hàng xóm v đã được thăm chưa. Điều này quan trọng để tránh lặp vô hạn trong đồ thị có chu trình và đảm bảo mỗi đỉnh chỉ được xử lý một lần từ "lớp" gần nhất.
visited[v] = true; q.push(v);: Nếu v chưa thăm, đánh dấu nó đã thăm và thêm vào hàng đợi để xử lý sau.

Khi chạy chương trình main, nó sẽ tạo một đồ thị nhỏ và thực hiện BFS từ đỉnh 0. Output sẽ là thứ tự các đỉnh được thăm theo chiều rộng.

Độ phức tạp của BFS

Độ phức tạp Thời gian: O(V + E), trong đó V là số đỉnh và E là số cạnh trong đồ thị. Giải thích:
- Mỗi đỉnh được đưa vào và lấy ra khỏi Queue tối đa một lần. Việc này mất O(V) thời gian tổng cộng.
- Đối với mỗi đỉnh, chúng ta duyệt qua danh sách kề của nó. Tổng số lượng các hàng xóm được duyệt qua trên toàn bộ đồ thị là tổng bậc của tất cả các đỉnh, bằng 2E trong đồ thị vô hướng (hoặc E trong đồ thị có hướng). Do đó, việc duyệt các cạnh mất O(E) thời gian.
- Kết hợp lại, tổng thời gian là O(V + E). Đây là hiệu quả, vì chúng ta chỉ cần nhìn vào mỗi đỉnh và mỗi cạnh một số lần cố định.
Độ phức tạp Không gian: O(V). Giải thích:
- Chúng ta cần một mảng visited có kích thước O(V) để lưu trạng thái thăm của các đỉnh.
- Trong trường hợp xấu nhất (ví dụ: đồ thị hình "sao" hoặc đồ thị đầy đủ), Queue có thể chứa gần như tất cả các đỉnh cùng một lúc. Do đó, Queue cần không gian O(V).
- Danh sách kề để biểu diễn đồ thị có thể cần O(V + E) không gian, nhưng độ phức tạp không gian của thuật toán BFS tự thân (auxiliary space) thường được xem là không gian cần thiết ngoài việc lưu trữ đồ thị, tức là O(V) cho Queue và mảng visited.

Ứng dụng quan trọng của BFS

BFS không chỉ là một kỹ thuật duyệt đồ thị đơn thuần; nó còn là nền tảng cho nhiều giải thuật và ứng dụng quan trọng. Dưới đây là một số ví dụ nổi bật:

Tìm đường đi ngắn nhất trên đồ thị không trọng số: Đây là ứng dụng quan trọng nhất của BFS. Bởi vì BFS khám phá các đỉnh theo từng lớp khoảng cách từ nguồn, đỉnh đích đầu tiên được tìm thấy chắc chắn nằm trên đường đi ngắn nhất (về số cạnh) từ đỉnh nguồn.
Kiểm tra tính liên thông và tìm các thành phần liên thông: Bằng cách chạy BFS từ một đỉnh chưa thăm bất kỳ, bạn có thể tìm thấy tất cả các đỉnh cùng thuộc một thành phần liên thông với đỉnh đó. Lặp lại quá trình này cho đến khi tất cả các đỉnh đều được thăm sẽ cho bạn biết số lượng và các đỉnh thuộc từng thành phần liên thông.
Kiểm tra đồ thị có phải là đồ thị hai phía (Bipartite Graph) không: Một đồ thị là hai phía nếu các đỉnh của nó có thể được chia thành hai tập hợp rời nhau sao cho không có cạnh nào nối hai đỉnh cùng thuộc một tập hợp. BFS có thể kiểm tra điều này bằng cách "tô màu" các đỉnh luân phiên. Bắt đầu với một đỉnh màu 0, tất cả hàng xóm của nó màu 1, tất cả hàng xóm chưa thăm của màu 1 sẽ màu 0, v.v. Nếu gặp một đỉnh đã có màu mà màu đó lại giống màu của hàng xóm của nó, thì đồ thị không phải hai phía.
Thuật toán tìm kiếm trong mê cung hoặc các bài toán trạng thái: Nhiều bài toán có thể được mô hình hóa thành việc tìm kiếm đường đi trong một "không gian trạng thái", nơi mỗi trạng thái là một đỉnh và các thao tác hợp lệ là các cạnh. Nếu chi phí của mỗi thao tác là như nhau (đồ thị không trọng số), BFS sẽ tìm ra chuỗi thao tác ngắn nhất để đi từ trạng thái bắt đầu đến trạng thái đích. Ví dụ điển hình là giải mê cung (tìm đường đi ngắn nhất theo số bước), bài toán 8-puzzle, v.v.
Web Crawlers: Các công cụ thu thập dữ liệu web có thể sử dụng BFS để duyệt các trang web. Bắt đầu từ một URL, nó thêm tất cả các liên kết trên trang đó vào hàng đợi và duyệt chúng theo thứ tự được thêm vào. Điều này giúp khám phá các trang web ở "độ sâu" nhỏ trước.
Garbage Collection (Thu gom rác): Trong một số thuật toán thu gom rác (ví dụ: Mark-and-Sweep), BFS được sử dụng để đánh dấu tất cả các đối tượng có thể truy cập được từ các "gốc" (root objects). Các đối tượng không được đánh dấu sẽ bị coi là "rác" và được giải phóng bộ nhớ.

Ví dụ Ứng dụng 1: Tìm Đường Đi Ngắn Nhất (theo số cạnh)

Chúng ta có thể dễ dàng mở rộng BFS để tìm độ dài đường đi ngắn nhất từ nguồn đến tất cả các đỉnh khác trong đồ thị không trọng số. Chúng ta chỉ cần duy trì một mảng distance lưu trữ khoảng cách từ đỉnh nguồn.

#include <iostream>
#include <vector>
#include <queue>
#include <limits> // Dành cho std::numeric_limits

// Hàm tìm khoảng cách ngắn nhất từ đỉnh nguồn đến tất cả các đỉnh khác
// trên đồ thị không trọng số bằng BFS.
std::vector<int> findShortestDistances(const std::vector<std::vector<int>>& adj, int start_node) {
    int num_vertices = adj.size();

    // Mảng lưu trữ khoảng cách từ start_node. Khởi tạo là -1 (chưa tới được)
    // hoặc một giá trị vô cùng lớn (nếu không dùng -1).
    // Ở đây dùng -1 để chỉ đỉnh chưa được thăm và chưa tính khoảng cách.
    std::vector<int> dist(num_vertices, -1); 

    std::queue<int> q;

    // Bắt đầu từ đỉnh nguồn. Khoảng cách là 0.
    dist[start_node] = 0;
    q.push(start_node);

    // Duyệt BFS
    while (!q.empty()) {
        int u = q.front();
        q.pop();

        // Duyệt qua các hàng xóm của u
        for (int v : adj[u]) {
            // Nếu hàng xóm v chưa được thăm (khoảng cách là -1)
            if (dist[v] == -1) {
                // Khoảng cách đến v bằng khoảng cách đến u + 1 (vì mỗi cạnh có trọng số 1)
                dist[v] = dist[u] + 1;
                // Thêm v vào queue để xử lý các đỉnh "lớp" tiếp theo
                q.push(v);
            }
            // Nếu v đã được thăm, tức là đã tính được khoảng cách đến v
            // từ một đường đi ngắn hơn hoặc bằng đường đi qua u.
            // Với đồ thị không trọng số, lần đầu tiên thăm v bằng BFS
            // sẽ luôn cho khoảng cách ngắn nhất, nên ta không cần làm gì thêm.
        }
    }

    // Trả về vector chứa khoảng cách đến tất cả các đỉnh.
    // dist[i] là khoảng cách từ start_node đến đỉnh i.
    // Nếu dist[i] là -1, nghĩa là đỉnh i không thể truy cập được từ start_node.
    return dist;
}

int main() {
    // Ví dụ đồ thị (số đỉnh = 5)
    std::vector<std::vector<int>> adj(5);

    adj[0].push_back(1);
    adj[0].push_back(2);

    adj[1].push_back(0);
    adj[1].push_back(3);
    adj[1].push_back(4);

    adj[2].push_back(0);
    adj[2].push_back(4);

    adj[3].push_back(1);

    adj[4].push_back(1);
    adj[4].push_back(2);

    int start_node = 0;
    std::vector<int> distances = findShortestDistances(adj, start_node);

    std::cout << "Khoang cach ngan nhat tu dinh " << start_node << ":" << std::endl;
    for (int i = 0; i < adj.size(); ++i) {
        if (distances[i] != -1) {
            std::cout << "Dinh " << i << ": " << distances[i] << std::endl;
        } else {
            std::cout << "Dinh " << i << ": Khong the toi duoc" << std::endl;
        }
    }

    return 0;
}

Giải thích Code:

std::vector<int> dist(num_vertices, -1);: Một vector dist được dùng thay cho mảng visited. Giá trị dist[i] sẽ lưu trữ khoảng cách ngắn nhất (số cạnh) từ start_node đến đỉnh i. Khởi tạo bằng -1 để biểu thị rằng đỉnh i chưa được thăm và khoảng cách chưa được xác định.
dist[start_node] = 0;: Khoảng cách từ đỉnh nguồn đến chính nó là 0.
if (dist[v] == -1): Thay vì kiểm tra visited[v] == false, chúng ta kiểm tra dist[v] == -1. Điều này có cùng ý nghĩa: đỉnh v chưa được thăm lần đầu tiên bởi BFS.
dist[v] = dist[u] + 1;: Khi thăm đỉnh v từ đỉnh u lần đầu tiên, khoảng cách đến v chính là khoảng cách đến u cộng thêm 1 (vì ta đi thêm một cạnh). Nhờ tính chất tầng lớp của BFS, đây là khoảng cách ngắn nhất.
Hàm trả về vector dist, cho phép truy cập khoảng cách đến bất kỳ đỉnh nào.

Ví dụ Ứng dụng 2: Kiểm tra Đồ thị Hai Phía (Bipartite)

BFS có thể được dùng để kiểm tra xem một đồ thị có phải là hai phía hay không. Ý tưởng là "tô màu" đồ thị bằng hai màu (ví dụ: 0 và 1) sao cho hai đỉnh kề nhau luôn có màu khác nhau.

#include <iostream>
#include <vector>
#include <queue>

// Hàm kiểm tra xem đồ thị có phải hai phía không bằng BFS
bool isBipartite(const std::vector<std::vector<int>>& adj) {
    int num_vertices = adj.size();

    // Mảng lưu màu của các đỉnh.
    // -1: Chưa tô màu
    //  0: Màu thứ nhất
    //  1: Màu thứ hai
    std::vector<int> color(num_vertices, -1); 

    // Đồ thị có thể không liên thông, cần lặp qua tất cả các đỉnh
    for (int start_node = 0; start_node < num_vertices; ++start_node) {
        // Chỉ bắt đầu BFS nếu đỉnh này chưa được tô màu (chưa thuộc thành phần nào)
        if (color[start_node] == -1) {
            std::queue<int> q;
            q.push(start_node);
            color[start_node] = 0; // Tô màu đầu tiên cho đỉnh bắt đầu

            while (!q.empty()) {
                int u = q.front();
                q.pop();

                // Duyệt qua các hàng xóm của u
                for (int v : adj[u]) {
                    // Nếu hàng xóm v chưa được tô màu
                    if (color[v] == -1) {
                        // Tô màu v khác màu của u
                        color[v] = 1 - color[u];
                        q.push(v);
                    } 
                    // Nếu hàng xóm v đã được tô màu VÀ màu của nó lại GIỐNG màu của u
                    else if (color[v] == color[u]) {
                        // Tìm thấy một cạnh nối hai đỉnh cùng màu -> Không phải đồ thị hai phía
                        return false;
                    }
                    // Nếu hàng xóm v đã được tô màu và màu của nó khác màu của u,
                    // điều này là hợp lệ, không cần làm gì thêm.
                }
            }
        }
    }

    // Nếu duyệt hết toàn bộ đồ thị mà không phát hiện xung đột màu nào
    // (hai đỉnh kề nhau có cùng màu), thì đồ thị là hai phía.
    return true;
}

int main() {
    // Ví dụ 1: Đồ thị hai phía (chu trình có độ dài chẵn)
    std::vector<std::vector<int>> adj1(4);
    adj1[0].push_back(1); adj1[1].push_back(0);
    adj1[0].push_back(3); adj1[3].push_back(0);
    adj1[1].push_back(2); adj1[2].push_back(1);
    adj1[2].push_back(3); adj1[3].push_back(2);
    // Đồ thị này là chu trình C4: 0-1-2-3-0. Là hai phía (0,2 thuộc 1 tập; 1,3 thuộc tập kia)

    std::cout << "Do thi 1 co phai hai phia? " << (isBipartite(adj1) ? "Co" : "Khong") << std::endl; // Output: Co

    // Ví dụ 2: Đồ thị không hai phía (chu trình có độ dài lẻ)
    std::vector<std::vector<int>> adj2(3);
    adj2[0].push_back(1); adj2[1].push_back(0);
    adj2[1].push_back(2); adj2[2].push_back(1);
    adj2[2].push_back(0); adj2[0].push_back(2);
    // Đồ thị này là chu trình C3: 0-1-2-0. Không hai phía.

    std::cout << "Do thi 2 co phai hai phia? " << (isBipartite(adj2) ? "Co" : "Khong") << std::endl; // Output: Khong

    // Ví dụ 3: Đồ thị có nhiều thành phần liên thông, một trong số đó không hai phía
     std::vector<std::vector<int>> adj3(6);
    // Thành phần 1 (hai phía): 0-1-2-1-0
    adj3[0].push_back(1); adj3[1].push_back(0);
    adj3[1].push_back(2); adj3[2].push_back(1);
    adj3[2].push_back(0); // Cạnh 2-0 tạo chu trình C3
    adj3[0].push_back(2);

    // Thành phần 2 (hai phía): 3-4-5-4-3
    adj3[3].push_back(4); adj3[4].push_back(3);
    adj3[4].push_back(5); adj3[5].push_back(4);

    std::cout << "Do thi 3 co phai hai phia? " << (isBipartite(adj3) ? "Co" : "Khong") << std::endl; // Output: Khong

    return 0;
}

Giải thích Code:

std::vector<int> color(num_vertices, -1);: Vector color lưu màu của mỗi đỉnh (-1: chưa tô, 0 hoặc 1: màu).
for (int start_node = 0; start_node < num_vertices; ++start_node): Vòng lặp này cần thiết để đảm bảo xử lý cả các đồ thị không liên thông. Nếu một đỉnh chưa được tô màu (color[start_node] == -1), nghĩa là nó thuộc một thành phần liên thông mới chưa được duyệt, ta bắt đầu một BFS từ đỉnh đó.
color[start_node] = 0;: Tô màu khởi đầu cho thành phần liên thông mới là 0.
color[v] = 1 - color[u];: Khi thăm một đỉnh v chưa được tô màu từ đỉnh u, ta gán cho v màu ngược lại với màu của u (1 - color[u]).
else if (color[v] == color[u]): Nếu v đã được tô màu và màu của nó lại giống màu của u (trong khi chúng kề nhau), đây là dấu hiệu đồ thị không phải hai phía, và hàm trả về false ngay lập tức.
Nếu BFS hoàn thành trên một thành phần liên thông mà không tìm thấy xung đột màu, thành phần đó là hai phía. Nếu tất cả các thành phần liên thông đều là hai phía, đồ thị tổng thể là hai phía, và hàm trả về true sau khi vòng lặp ngoài kết thúc.

Ưu điểm và Nhược điểm của BFS

Ưu điểm:

Tìm đường đi ngắn nhất trên đồ thị không trọng số: Đây là ưu điểm lớn nhất và đặc trưng của BFS.
Đảm bảo tìm thấy tất cả các đỉnh có thể truy cập được: BFS duyệt mọi đỉnh trong thành phần liên thông của đỉnh nguồn.
Dễ hiểu và triển khai: Sử dụng Queue và mảng visited là khá trực quan.

Nhược điểm:

Tiêu tốn nhiều bộ nhớ: Trong trường hợp xấu nhất, Queue có thể chứa rất nhiều đỉnh, đặc biệt với các đồ thị có bậc trung bình cao hoặc đồ thị dày đặc. Điều này có thể gây ra lỗi tràn bộ nhớ (out of memory) với đồ thị lớn.
Không hiệu quả với đồ thị có trọng số: BFS không thể tìm đường đi ngắn nhất trên đồ thị có trọng số dương (cần thuật toán khác như Dijkstra) hoặc trọng số âm (cần Bellman-Ford).

Khi nào sử dụng BFS?

Hãy cân nhắc sử dụng BFS khi:

Bạn cần tìm đường đi ngắn nhất theo số lượng cạnh (đồ thị không trọng số).
Bạn muốn khám phá đồ thị theo từng "lớp" hoặc "tầng" khoảng cách từ đỉnh nguồn.
Bạn cần kiểm tra các thuộc tính liên quan đến khoảng cách trên đồ thị không trọng số (ví dụ: tính hai phía).
Bạn đang giải quyết các bài toán tìm kiếm trong không gian trạng thái mà chi phí di chuyển giữa các trạng thái là như nhau.

Bài tập ví dụ:

[Graph].BFS trên đồ thị có hướng.

Cho đồ thị có hướng G = (V, E) được biểu diễn dưới dạng danh sách cạnh. Hãy thực hiện in ra danh sách các đỉnh được duyệt theo thuật toán BFS(s).

Input Format

Dòng đầu tiên là 2 số n và m và s, tương ứng với số lượng đỉnh, cạnh của đồ thị và đỉnh bắt đầu duyệt. Các đỉnh của đồ thị được đánh số từ 1 tới n. m dòng tiếp theo mỗi dòng chứa đỉnh u, v (u != v) tương ứng với một cạnh của đồ thị. (1<=s<=n<=1000; 1<=m<=n*(n-1)/2)

Constraints

Output Format

In ra các đỉnh được duyệt theo thuật toán BFS(s). Chú ý trong quá trình mở rộng các đỉnh của thuật toán BFS luôn lựa chọn duyệt các đỉnh có thứ tự nhỏ hơn trước.

Ví dụ:

Dữ liệu vào

Dữ liệu ra

1 2 3 4 5

Đây là hướng dẫn giải bài toán BFS trên đồ thị có hướng với yêu cầu in đỉnh theo thứ tự nhỏ hơn trước:

Đọc input: Đọc số đỉnh n, số cạnh m và đỉnh bắt đầu s.
Biểu diễn đồ thị: Sử dụng danh sách kề (adjacency list). Vì đồ thị có hướng, khi đọc cạnh u v, chỉ thêm v vào danh sách kề của u. Nên dùng std::vector<std::vector<int>> để lưu danh sách kề. Các đỉnh đánh số từ 1 nên cần kích thước n+1.
Xử lý ràng buộc "đỉnh nhỏ hơn trước": Sau khi đọc hết các cạnh và xây dựng danh sách kề, duyệt qua từng danh sách kề của mỗi đỉnh và sắp xếp nó theo thứ tự tăng dần. Sử dụng std::sort cho việc này.
Khởi tạo BFS:
- Sử dụng một mảng boolean visited (kích thước n+1, khởi tạo false) để đánh dấu các đỉnh đã thăm.
- Sử dụng một hàng đợi (queue) std::queue<int> để lưu các đỉnh cần thăm.
- Đưa đỉnh bắt đầu s vào hàng đợi.
- Đánh dấu đỉnh s là đã thăm (visited[s] = true).
Thực hiện BFS:
- Trong khi hàng đợi còn phần tử:
  - Lấy đỉnh u ở đầu hàng đợi ra.
  - In đỉnh u.
  - Duyệt qua danh sách kề đã sắp xếp của u. Với mỗi đỉnh kề v:
    - Nếu v chưa được thăm (visited[v] == false):
      - Đánh dấu v là đã thăm (visited[v] = true).
      - Đưa v vào hàng đợi.

Làm thêm nhiều bài tập miễn phí tại đây

Comments

There are no comments at the moment.