Thuật toán BFS (Breadth-First Search) là gì? Giải thích dễ hiểu kèm demo trực quan

Thuật toán BFS (Breadth-First Search) là gì? Giải thích dễ hiểu kèm demo trực quan

BFS (Breadth-First Search) là thuật toán duyệt và tìm kiếm trên đồ thị theo kiểu “đi từng lớp” (layer). Thay vì đi sâu vào một nhánh như DFS, BFS sẽ đi lần lượt qua tất cả các đỉnh ở khoảng cách 1 cạnh, rồi tới khoảng cách 2 cạnh, 3 cạnh, … tính từ đỉnh bắt đầu.

Nếu mỗi cạnh có cùng “chi phí” (hoặc không có trọng số), BFS đồng thời cũng là thuật toán tìm đường đi ngắn nhất theo số cạnh giữa hai đỉnh.

BFS giải bài toán gì?

• Duyệt toàn bộ đồ thị theo từng lớp (layer).
• Tìm đường đi ngắn nhất (theo số cạnh) giữa hai đỉnh trên đồ thị không trọng số.
• Kiểm tra xem một đỉnh có thể đi tới đỉnh khác được hay không (tính liên thông).
• Làm “xương sống” cho nhiều thuật toán đồ thị khác (tìm khoảng cách, phân tích mạng, lan truyền, …).

Ý tưởng chính của BFS

BFS sử dụng một cấu trúc dữ liệu chính là hàng đợi (queue):

1. Chọn đỉnh bắt đầu, đánh dấu là đã thăm (visited) và cho vào queue.
2. Lặp cho đến khi queue rỗng:
   • Lấy một đỉnh ở đầu queue ra (gọi là current).
   • Xét tất cả hàng xóm (neighbor) của current.
   • Nếu neighbor chưa được thăm:
     • Đánh dấu là đã thăm.
     • Lưu lại “đỉnh trước đó” (previous) để sau này truy vết đường đi.
     • Đưa neighbor vào cuối queue.

Nhờ duyệt theo từng lớp như vậy, BFS đảm bảo khi ta gặp đỉnh đích lần đầu tiên thì đó chính là đường đi ngắn nhất (tính theo số cạnh) từ nguồn đến đích.

Độ phức tạp

• Thời gian: O(V + E) (V là số đỉnh, E là số cạnh).
• Bộ nhớ: O(V) cho queue + mảng visited + previous.

Ví dụ đồ thị minh họa

Dùng một đồ thị nhỏ với các đỉnh từ A đến F:

A: B, C
B: A, D, E
C: A, F
D: B
E: B, F
F: C, E

Đồ thị là vô hướng: nếu có A – B thì đi được cả chiều A → B và B → A.

Demo BFS bằng JavaScript (tìm đường đi ngắn nhất theo số cạnh)

Demo dưới đây cho phép bạn chọn đỉnh bắt đầu và đỉnh kết thúc, sau đó chạy BFS để:

• Hiển thị trạng thái từng đỉnh: đã thăm hay chưa, đỉnh hiện tại.
• Hiển thị hàng đợi (queue) ở mỗi bước.
• Log từng bước: lấy đỉnh nào ra khỏi queue, đẩy đỉnh nào vào.
• Xây dựng lại đường đi ngắn nhất (nếu có) từ nguồn đến đích.

Phân tích đoạn code BFS

1. Cấu trúc đồ thị và BFS lưu bước

var graph = {
    A: ["B", "C"],
    B: ["A", "D", "E"],
    C: ["A", "F"],
    D: ["B"],
    E: ["B", "F"],
    F: ["C", "E"]
};

var nodes = ["A", "B", "C", "D", "E", "F"];

function bfsWithSteps(start, end) {
    var visited = {};
    var prev = {};
    var queue = [];
    var steps = [];

    nodes.forEach(function(n) {
        visited[n] = false;
        prev[n] = null;
    });

    visited[start] = true;
    queue.push(start);

    steps.push({
        type: "enqueue",
        node: start,
        from: null,
        queue: queue.slice(),
        visited: Object.assign({}, visited)
    });

    while (queue.length > 0) {
        var current = queue.shift();

        steps.push({
            type: "dequeue",
            node: current,
            queue: queue.slice(),
            visited: Object.assign({}, visited)
        });

        if (current === end) {
            break;
        }

        graph[current].forEach(function(nei) {
            if (!visited[nei]) {
                visited[nei] = true;
                prev[nei] = current;
                queue.push(nei);

                steps.push({
                    type: "enqueue",
                    node: nei,
                    from: current,
                    queue: queue.slice(),
                    visited: Object.assign({}, visited)
                });
            }
        });
    }

    return {
        steps: steps,
        prev: prev
    };
}

2. Xây dựng lại đường đi từ prev

function buildPath(prev, start, end) {
    var path = [];
    var cur = end;

    while (cur !== null) {
        path.unshift(cur);
        if (cur === start) break;
        cur = prev[cur];
    }

    if (path[0] !== start) return null;
    return path;
}

Khi nào nên dùng BFS?

• Khi đồ thị không trọng số (hoặc các cạnh có “chi phí” như nhau).
• Khi cần đường đi ngắn nhất theo số bước giữa hai đỉnh.
• Khi cần duyệt đồ thị theo từng lớp (tìm tất cả node cách nguồn 1 bước, 2 bước, …).

Kết luận

BFS là một trong những thuật toán cơ bản nhưng cực kỳ quan trọng trong xử lý đồ thị. Nó không chỉ dùng để duyệt mà còn là nền tảng để xây dựng rất nhiều thuật toán nâng cao khác.

Với demo trực quan trên, từng bước enqueue/dequeue, đánh dấu visited và xây dựng đường đi đều được minh hoạ rõ ràng, giúp việc nắm bắt BFS trở nên cực kỳ dễ chịu.