BFS — Breadth-First Search và unweighted shortest path

TL;DR: BFS (Breadth-First Search) duyệt graph theo từng "lớp" bằng queue FIFO: tất cả đỉnh cách nguồn 1 cạnh trước, rồi 2 cạnh, rồi 3 cạnh, không bao giờ nhảy cóc. Nhờ đó lần đầu BFS chạm tới một vertex luôn là qua đường ngắn nhất (ít cạnh nhất), nên BFS cho đường ngắn nhất trên unweighted graph (graph không trọng số) trong O(V+E) time, O(V) space. Bẫy lớn nhất: BFS sai hoàn toàn trên weighted graph, vì "ít cạnh nhất" không còn nghĩa là "tổng weight nhỏ nhất"; lúc đó phải dùng Dijkstra.

Bạn cần tìm đường ngắn nhất từ server A đến server B trong mạng nội bộ, không phải đường "ít km nhất" mà là đường "ít hop nhất". Hoặc bài toán "sáu bậc kết nối" của LinkedIn: người X cách người Y bao nhiêu bậc? Hoặc web crawler muốn ưu tiên URL gần trang gốc hơn URL sâu 10 cấp.

Cả ba bài toán có cùng cấu trúc: graph không có weight (hoặc coi mọi cạnh có weight 1), cần đường ít cạnh nhất. BFS giải cả ba trong O(V + E) và đảm bảo đường tìm được là ngắn nhất (ít cạnh nhất).

Bài này dạy BFS từ cách queue hoạt động, cách theo dõi từng level, cách tính khoảng cách và dựng lại đường đi qua parent, cùng các dạng hay gặp trong system design.

1. Hình dung: Lan tỏa sóng nước

Quẳng một viên đá vào hồ tĩnh lặng. Sóng lan ra thành từng vòng tròn đều nhau: vòng thứ nhất cách điểm rơi 1 đơn vị, vòng thứ hai cách 2, vòng thứ ba cách 3. Điểm nào trên mặt hồ cách chỗ đá rơi N đơn vị thì sóng chạm tới sau đúng N "giây".

BFS chạy y hệt: bắt đầu từ start, duyệt tất cả vertex cách 1 cạnh, rồi cách 2 cạnh, rồi 3 cạnh, không nhảy cóc. Nên lần đầu BFS "chạm" tới một vertex, đó chắc chắn là qua đường ngắn nhất.

2. Thuật toán BFS — cơ chế

BFS dùng queue (FIFO) để duyệt theo level. Đổi sang stack thì thành DFS, và không còn đảm bảo đường ngắn nhất.

BFS(G, start):
    dist[start] <- 0
    dist[v] <- INF cho mọi v != start
    parent[v] <- NIL cho mọi v

    Q <- Queue rỗng
    Q.enqueue(start)

    while Q không rỗng:
        v <- Q.dequeue()               -- lấy đỉnh đầu hàng
        for each đỉnh u kề v trong G:
            if dist[u] = INF:          -- chưa thăm
                dist[u] <- dist[v] + 1
                parent[u] <- v         -- ghi lại để dựng lại path
                Q.enqueue(u)

    return dist, parent
    -- dist[v] = INF nếu v không thể tới từ start

Time: O(V+E) Space: O(V)

Ý chính: vì queue là FIFO, mọi vertex ở level k được dequeue trước bất kỳ vertex level k+1 nào. Điều này đảm bảo đường tìm được là ngắn nhất.

Sóng BFS lan từ start: level 1 gồm A và B, level 2 gồm C, D, E (D đến được từ cả A lẫn B nhưng chỉ visit một lần, lần đầu), level 3 chỉ còn F.

3. Pseudocode đầy đủ — distance + path reconstruction

Mục 2 đã cho dist và parent. Muốn lấy đường đi cụ thể thì thêm hai bước: thoát sớm khi gặp đích, rồi đi ngược theo parent từ đích về nguồn.

-- Trả về shortest path từ start đến target.
-- Trả về danh sách rỗng nếu không thể tới.
BFS_path(G, start, target):
    n <- số đỉnh của G
    dist[0..n-1] <- INF
    parent[0..n-1] <- -1
    dist[start] <- 0
    Q <- Queue rỗng
    Q.enqueue(start)

    while Q không rỗng:
        v <- Q.dequeue()
        if v = target:
            break                       -- tìm thấy, thoát sớm
        for each đỉnh u kề v:
            if dist[u] = INF:
                dist[u] <- dist[v] + 1
                parent[u] <- v          -- đánh dấu đã thăm khi push
                Q.enqueue(u)

    if dist[target] = INF: return []    -- không thể tới

    -- Dựng lại path: đi ngược từ target về start
    path <- []
    cur <- target
    while cur != -1:
        path.prepend(cur)
        cur <- parent[cur]
    return path

Time: O(V+E) Space: O(V)

3.1 Trace ví dụ — graph 6 đỉnh

Graph: 0-1, 0-2, 1-3, 1-4, 2-4, 3-5. BFS từ đỉnh 0. Bảng dưới là một bảng trace: mỗi dòng là một lượt lặp, mỗi cột là một biến. Nếu chưa quen đọc và vẽ kiểu này, ôn lại Bảng trace.

Graph:
  0 -- 1 -- 3 -- 5
  |    |
  2 -- 4

Kết quả: dist = [0, 1, 1, 2, 2, 3]. Đỉnh 5 cách 0 đúng 3 cạnh (0→1→3→5).

Thử ngẫmtrace ở trên chốt dist[4] = 2 ngay lúc enqueue ở bước 2, dù đỉnh 4 còn nằm chờ trong queue tới bước 3. Đổi sang set dist[u] lúc dequeue thay vì lúc enqueue, kết quả dist[] có còn đúng shortest path không?

4. Vì sao BFS đảm bảo shortest path trên unweighted graph

Queue FIFO ép BFS duyệt theo level. Nói cụ thể:

Bất biến (invariant), tức điều luôn đúng trong suốt quá trình chạy: queue chỉ chứa vertex ở level k rồi tới level k+1, xếp theo thứ tự level tăng dần, không bao giờ lẫn hơn 2 level liên tiếp.

Vì sao dist đúng: giả sử đỉnh u có đường ngắn nhất d cạnh, và w là đỉnh ngay trước u trên đường đó (dist[w] = d - 1). Theo bất biến, w được lấy ra khỏi queue trước mọi đỉnh ở level d. Lúc w được xử lý, u hoặc đã có dist = d từ trước, hoặc được gán d ngay lúc đó. Không có cách nào để u nhận giá trị lớn hơn d.

Điều kiện unweighted: mỗi cạnh phải có weight bằng 1. Khi weight các cạnh khác nhau, "ít cạnh nhất" không còn là "tổng weight nhỏ nhất". Weighted graph cần Dijkstra (bài 05).

5. Complexity

Time O(V + E): mỗi vertex được enqueue đúng một lần (vì mark visited trước khi push). Mỗi cạnh được kiểm tra một lần (hai lần với undirected graph, vẫn là O(E)). Tổng: O(V + E). Nhìn bề ngoài là hai vòng lặp lồng nhau, nhưng vòng trong không chạy V lần cho mỗi đỉnh: tổng số lượt của nó trên mọi đỉnh chỉ là số cạnh. Nếu muốn ôn cách đếm vòng lặp lồng, xem Lặp lồng nhau.

Space O(V): queue chứa tối đa V vertex. Mảng dist[] và parent[] mỗi cái O(V).

6. Level tracking — pattern phổ biến

Đôi khi bạn cần xử lý riêng từng level chứ không chỉ lấy distance, ví dụ in các node của tree theo từng level, hay tìm diameter (khoảng cách xa nhất giữa hai node) của tree.

BFS_by_level(G, start):
    Q <- Queue rỗng
    Q.enqueue(start)
    visited <- Set {start}
    level <- 0

    while Q không rỗng:
        size <- Q.size()               -- chụp lại số node ở level hiện tại
        for i <- 0 đến size-1:
            v <- Q.dequeue()
            -- xử lý v ở level 'level' tại đây
            for each đỉnh u kề v:
                if u không trong visited:
                    visited.add(u)
                    Q.enqueue(u)
        level <- level + 1

Time: O(V+E) Space: O(V)

Mấu chốt: chụp lại size trước vòng lặp trong. Khi bắt đầu xử lý level k, queue chỉ chứa node level k. Vòng lặp trong xử lý đúng size node đó; các node level k+1 được thêm vào cuối queue nhưng chưa xử lý ở lượt này.

Ứng dụng thực tế:

• LeetCode 102 — Binary Tree Level Order Traversal: in node theo từng level.
• Sáu bậc kết nối: đếm level cho đến khi gặp user đích.
• Tìm diameter của tree: BFS từ một node bất kỳ, lấy node xa nhất, rồi BFS lại từ node đó; distance xa nhất tìm được chính là diameter.

Thử ngẫmchụp size trước vòng lặp trong là để tách level k khỏi level k+1 vừa được thêm vào cuối queue. Bỏ bước đó đi, level order traversal của LeetCode 102 sẽ sai ở đâu?

7. Bẫy tổng hợp

Bẫy 1: Mark visited khi POP thay khi PUSH

-- BUG: đánh dấu đã thăm khi dequeue, không phải khi enqueue
while Q không rỗng:
    v <- Q.dequeue()
    dist[v] <- dist_tinh_duoc   -- quá muộn -- v có thể đã ở trong Q nhiều lần
    for each đỉnh u kề v:
        if dist[u] = INF:
            Q.enqueue(u)        -- u có thể bị enqueue nhiều lần trước khi visited

Time: O(V+E) Space: O(V)

Nếu vertex u có 3 neighbor cùng chưa visited, u bị enqueue 3 lần, và cả 3 bản sao đều bị mở rộng lại khi tới lượt. Số bản sao nhân lên theo từng level: trên graph mà mỗi tầng có 2 đỉnh nối đầy đủ với tầng kế (chạy thử bằng tay hoặc bằng script nháp), số lần enqueue là 7, 63, 511, 4095 sau 2, 5, 8, 11 tầng, tức tăng theo cấp số mũ. Nếu bạn có thêm dòng "bỏ qua nếu đã visited" khi pop thì thời gian về lại O(V + E), nhưng queue vẫn phình tới O(E) phần tử. Đánh dấu ngay khi enqueue tránh được cả hai chuyện.

-- CORRECT: đánh dấu đã thăm TRƯỚC khi enqueue
for each đỉnh u kề v:
    if dist[u] = INF:           -- chưa visited
        dist[u] <- dist[v] + 1  -- đánh dấu khi push
        Q.enqueue(u)

Time: O(V+E) Space: O(V)

Bẫy 2: Dùng BFS cho weighted graph

BFS sai hoàn toàn khi weight các cạnh không đều nhau.

-- Graph: A --(weight 5)--> B,  A --(weight 1)--> C --(weight 1)--> B
-- BFS chỉ đếm cạnh, không đếm weight:
-- BFS tìm A->B = 1 cạnh, trả về path [A, B], "distance" = 1
-- Nhưng tổng weight = 5
-- Path A->C->B có 2 cạnh nhưng tổng weight = 2 -- ngắn hơn!
-- BFS bỏ qua path này vì "nhiều cạnh hơn"
-- => Dùng Dijkstra (bài 05) thay thế

Với weighted graph, hãy dùng Dijkstra (bài 05). BFS chỉ đúng khi mọi cạnh có weight bằng nhau.

Bẫy 3: Stack thay queue nhầm

Dùng Stack.push/pop (LIFO) thay cho Queue.enqueue/dequeue (FIFO) là chuyển từ BFS sang DFS, và không còn đảm bảo đường ngắn nhất.

8. Multi-source BFS

Bài toán: mạng lưới có nhiều nguồn (gateway, trạm sạc, bệnh viện). Với mỗi vertex, tìm khoảng cách đến nguồn gần nhất.

Cách ngây thơ (naive): chạy BFS riêng từ từng nguồn rồi lấy min. K nguồn × O(V + E) = O(K × (V + E)), với K lớn thì quá chậm.

Multi-source BFS: push tất cả nguồn vào queue ban đầu với distance 0. Chạy BFS đúng một lần: sóng lan từ tất cả nguồn cùng lúc, vertex nào bị chạm trước thì gần nguồn đó nhất.

BFS_multi_source(G, sources):
    dist[v] <- INF cho mọi v
    Q <- Queue rỗng

    for each s trong sources:
        dist[s] <- 0             -- mỗi nguồn có distance = 0
        Q.enqueue(s)

    while Q không rỗng:
        v <- Q.dequeue()
        for each đỉnh u kề v:
            if dist[u] = INF:
                dist[u] <- dist[v] + 1
                Q.enqueue(u)

    return dist   -- dist[v] = khoảng cách tới source gần nhất

Time: O(V+E) Space: O(V)

Độ phức tạp là O(V + E): chỉ chạy một lần BFS, K lớn đến đâu cũng không đổi.

Ứng dụng thực tế:

• LeetCode 994 — Rotting Oranges: nhiều quả cam thối cùng lan ra một lúc.
• LeetCode 542 — 01 Matrix: tìm distance từ mỗi cell đến cell 0 gần nhất.
• Quy hoạch bệnh viện: tìm khu dân cư xa mọi bệnh viện nhất.

Thử ngẫmmulti-source BFS chạy một lần cho K nguồn, độ phức tạp vẫn O(V+E), không phụ thuộc K. Nếu Rotting Oranges chỉ có 1 quả cam thối thay vì nhiều, thuật toán có gì khác không?

9. Bidirectional BFS — advanced

Bài toán: tìm đường từ A đến B trên graph rất lớn, như "sáu bậc" của Wikipedia hay social network hàng tỉ node.

BFS thường từ A: phải duyệt O(b^d) node (b là số nhánh con mỗi node, d là độ dài đường đi). Với b = 10 và d = 6, đó là 10^6 = 1 triệu node.

Bidirectional BFS: chạy hai BFS cùng lúc, một từ A đi tới, một từ B đi lui. Dừng khi hai frontier (rìa vùng đã duyệt) gặp nhau.

Mỗi BFS chỉ cần duyệt đến độ sâu d/2. Chi phí: O(2 × b^(d/2)). Với b = 10, d = 6: 2 × 10^3 = 2000 node, ít hơn 1 triệu node gấp 500 lần.

BFS_bidirectional(G, s, t):
    if s = t: return 0

    dist_s[s] <- 0;  dist_t[t] <- 0
    Q_s <- Queue{s};  Q_t <- Queue{t}

    while Q_s không rỗng hoặc Q_t không rỗng:
        result <- expand(G, Q_s, dist_s, dist_t)
        if result != -1: return result
        result <- expand(G, Q_t, dist_t, dist_s)
        if result != -1: return result
    return -1   -- không thể tới

expand(G, Q, dist_mine, dist_other):
    if Q rỗng: return -1
    v <- Q.dequeue()
    for each đỉnh u kề v:
        if u không trong dist_mine:
            dist_mine[u] <- dist_mine[v] + 1
            Q.enqueue(u)
            if u trong dist_other:
                return dist_mine[u] + dist_other[u]  -- meeting point
    return -1

Time: O(b^(d/2)) Space: O(b^(d/2))

Bản trên là bản rút gọn, trả về ngay lần gặp đầu tiên. Khi chạy thử trên nhiều graph ngẫu nhiên nhỏ, vẫn có trường hợp lần gặp đầu cho kết quả lớn hơn đường ngắn nhất thật. Bản đúng mở rộng trọn một level cho mỗi phía rồi lấy min của dist_s[u] + dist_t[u] trên mọi đỉnh mà hai phía cùng đã chạm (xem câu tự kiểm tra 5).

Ứng dụng: Wikipedia game (tìm đường từ bài A đến bài B qua hyperlink), tìm chuỗi kết nối ngắn nhất trong social network, tìm đường GPS trên bản đồ lớn.

10. Ứng dụng thực tế trong system design

Web crawler: BFS khớp rất tự nhiên với crawling. URL xuất phát là start, mỗi hyperlink là một cạnh. BFS giúp crawler ưu tiên URL gần trang gốc, tránh sa vào những nhánh sâu vô tận. Level chính là "độ sâu crawl". Hầu hết crawler thật giới hạn độ sâu tối đa để không crawl mãi.

Sáu bậc kết nối trên mạng xã hội: bidirectional BFS giữa 2 profile. Graph có hàng tỉ node nên BFS một chiều quá chậm; hai BFS gặp nhau ở giữa thì mỗi hướng chỉ cần duyệt một vùng nhỏ hơn nhiều.

Flooding có giới hạn TTL: trong mạng ngang hàng kiểu Gnutella, một truy vấn được gửi tràn cho mọi hàng xóm, và mỗi lần chuyển tiếp thì TTL (Time To Live) giảm 1. TTL chính là độ sâu BFS tối đa, giúp truy vấn không quay vòng mãi trên graph có cycle.

11. Đào sâu

Bài liên quan trong khoá học:

• Queue & Deque: hàng đợi FIFO vận hành BFS.
• Dijkstra: mở rộng BFS cho đồ thị có trọng số dương.

12. Tóm tắt

• BFS dùng queue FIFO, duyệt từng level từ gần đến xa, nên lần đầu visit một vertex là qua đường ít cạnh nhất. Chỉ đúng trên unweighted graph; weighted graph cần Dijkstra.
• O(V + E) time, O(V) space, với điều kiện mark visited khi PUSH, không phải khi POP.
• Level tracking: chụp lại size trước vòng trong để xử lý riêng từng level.
• Multi-source BFS: đưa mọi nguồn vào queue từ đầu, chạy một lần, O(V + E) bất kể số nguồn.
• Bidirectional BFS: hai BFS gặp nhau ở giữa, giảm O(b^d) xuống O(b^(d/2)).

13. Tự kiểm tra

Bài tiếp theo: DFS — preorder/postorder, cycle detection