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ờ đó vertex được visit lần đầu luôn qua path ngắn nhất (ít cạnh nhất), đảm bảo shortest path trên unweighted graph trong O(V+E) time, O(V) space. Pitfall lớn nhất: BFS sai hoàn toàn trên weighted graph — "ít cạnh nhất" không còn nghĩa là "tổng weight nhỏ nhất"; cần Dijkstra thay thế.

Bạn cần tìm đường ngắn nhất từ server A đến server B trong topology mạng nội bộ — không phải đường "ít km nhất", mà đường "ít hop nhất". Hoặc bài toán LinkedIn 6-degree separation: người X cách người Y bao nhiêu bậc kết nối? Hoặc web crawler muốn ưu tiên URL gần root 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 mọi cạnh coi như weight bằng 1), cần path ít cạnh nhất. BFS giải quyết tất cả trong O(V + E) — và đảm bảo path tìm được là shortest (ít cạnh nhất).

Bài này dạy BFS từ queue mechanics, level tracking, distance + parent reconstruction, và pattern hay gặp trong system design.

1. Analogy — Lan tỏa sóng nước

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

BFS hoạt động y hệt: bắt đầu từ start, duyệt tất cả vertex cách 1 cạnh, rồi tất cả cách 2 cạnh, rồi 3 cạnh — không bao giờ nhảy cóc. Kết quả là khi BFS "chạm" đến một vertex lần đầu, đó chắc chắn là qua path ngắn nhất.

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

BFS dùng queue (FIFO) để đảm bảo duyệt theo level. Không dùng stack — stack sẽ cho DFS, không còn guarantee shortest path.

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)

Key insight: vì queue là FIFO, mọi vertex ở level k được dequeue ra trước bất kỳ vertex level k+1 nào. Đây chính là điều đảm bảo shortest path.

graph LR
    START((start<br/>tầng 0)) --> A((A<br/>tầng 1))
    START --> B((B<br/>tầng 1))
    A --> C((C<br/>tầng 2))
    A --> D((D<br/>tầng 2))
    B --> D
    B --> E((E<br/>tầng 2))
    D --> F((F<br/>tầng 3))

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

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

-- Trả về distance[] từ start đến mọi đỉnh.
-- dist[v] = INF nghĩa là không thể tới.
BFS_distance(G, start):
    n <- số đỉnh của G
    dist[0..n-1] <- INF
    dist[start] <- 0
    Q <- Queue rỗng
    Q.enqueue(start)

    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

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

-- 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

    -- Reconstruct 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.

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 đảm bảo duyệt theo level. Cụ thể hơn:

Bất biến (invariant): tại mọi thời điểm, queue chỉ chứa vertex ở level k hoặc level k+1 — không bao giờ lẫn lộn nhiều hơn 2 level liên tiếp.

Chứng minh shortest path: giả sử BFS tìm đường đến vertex u qua path dài d. Nếu tồn tại path ngắn hơn d' (nhỏ hơn d), thì trên path đó có vertex w là "cha" của u với distance[w] = d' - 1. Nhưng level d' - 1 nhỏ hơn d - 1 — vertex w đã được dequeue ra trước vertex cha của u trên path dài hơn. Vì vậy u đã được visit từ w trước, với distance d' — mâu thuẫn với giả thiết BFS tìm path dài hơn.

Yêu cầu unweighted: mỗi cạnh phải có weight bằng 1. Khi cạnh có weight khác nhau, "ít cạnh nhất" không còn đồng nghĩa với "tổng weight nhỏ nhất". Weighted graph cần Dijkstra (lesson 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 edge được kiểm tra đúng một lần (hoặc hai lần với undirected graph — vẫn là O(E)). Tổng: O(V + E).

Space O(V): queue chứa tối đa V vertex. Mảng dist[] và parent[] mỗi cái O(V). Trong bipartite-like graph, queue có thể chứa khoảng V/2 vertex cùng lúc — vẫn O(V).

6. Level tracking — pattern phổ biến

Đôi khi không chỉ cần distance mà cần xử lý theo từng level riêng biệt — ví dụ in tất cả node theo level trong tree, hay tìm diameter của graph.

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()               -- snapshot số lượng 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)

Key pattern: snapshot size trước vòng lặp inner. Khi bắt đầu xử lý level k, queue chỉ chứa node level k. Vòng lặp inner xử lý đúng size node đó — các node level k+1 được thêm vào tail nhưng không được xử lý trong iteration này.

Use case thực tế:

• LeetCode 102 — Binary Tree Level Order Traversal: in node theo từng level.
• 6-degree separation: đếm level đến khi gặp target user.
• Tìm diameter của tree: BFS từ bất kỳ node, lấy node xa nhất, BFS lại từ đó — diameter là distance tìm được.

Thử ngẫmlevel tracking snapshot size trước vòng lặp inner để tách đúng level k khỏi level k+1 vừa được thêm vào tail. Bỏ bước snapshot đó, in level order traversal của LeetCode 102 sẽ sai ở đâu?

7. Pitfall tổng hợp

Pitfall 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 đều chưa visited, u sẽ bị enqueue 3 lần. Với dense graph, mỗi đỉnh có thể bị enqueue tối đa một lần cho mỗi cạnh đi vào nó (indegree lần), nên tổng enqueue lên đến O(E) — queue phình to và công việc thực tế tăng lên khoảng O(V·E) trong trường hợp tệ (vẫn là đa thức, không phải mũ). Đây là lý do mark-khi-enqueue giữ đúng O(V+E).

-- 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)

Pitfall 2 — Dùng BFS cho weighted graph

BFS sai hoàn toàn khi graph có weight không đều.

-- 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 (lesson 05) thay thế

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

Pitfall 3 — Stack thay queue nhầm

-- BUG: dùng Stack thay Queue
S <- Stack rỗng
S.push(start)

while S không rỗng:
    v <- S.pop()       -- LIFO -- đây là DFS, không phải BFS
    for each đỉnh u kề v:
        if chưa thăm:
            đánh dấu đã thăm
            S.push(u)
-- Không guarantee shortest path

Thay Stack.push/pop bằng Queue.enqueue/dequeue — chuyển từ LIFO sang FIFO, từ DFS sang BFS.

8. Multi-source BFS

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

Naive approach: BFS từ mỗi nguồn riêng, lấy min. K nguồn × O(V + E) = O(K × (V + E)). Với K lớn, quá chậm.

Multi-source BFS: push tất cả nguồn vào queue ban đầu với distance 0. Chạy BFS một lần duy nhất — sóng lan từ tất cả nguồn đồng thời. 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 source 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)

Complexity: O(V + E) — chỉ chạy một BFS duy nhất, không quan tâm K lớn đến đâu.

Ứng dụng thực tế:

• LeetCode 994 — Rotting Oranges: nhiều quả cam thối lan ra đồng thời.
• LeetCode 542 — 01 Matrix: tìm distance từ mỗi cell đến cell 0 gần nhất.
• Hospital location planning: tìm khu vực dân cư xa tất cả bệnh viện nhất.

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

9. Bidirectional BFS — advanced

Bài toán: path-finding A đến B trên graph rất lớn — Wikipedia 6-degree, social network với hàng tỉ node.

Naive BFS từ A: explore O(b^d) node (b = branching factor, d = path length). Với b = 10 và d = 6, đó là 10^6 = 1 triệu node.

Bidirectional BFS: chạy hai BFS đồng thời — một từ A tiến về phía trước, một từ B tiến ngược lại. Dừng khi hai frontier gặp nhau.

Mỗi BFS chỉ cần explore đến depth d/2. Chi phí: O(2 × b^(d/2)). Với b = 10, d = 6: 2 × 10^3 = 2000 node — nhỏ hơn 1 triệu 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))

Use case: Wikipedia game (tìm path từ bài A đến bài B qua hyperlink), social network shortest connection, GPS routing trên map lớn.

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

Web crawler: BFS tự nhiên cho crawling. Start URL là start, mỗi hyperlink là cạnh. BFS đảm bảo crawler ưu tiên URL gần root — tránh deep rabbit hole. Level = "crawl depth". Hầu hết production crawler giới hạn max depth để tránh infinite crawl.

LinkedIn / Facebook 6-degree separation: bidirectional BFS giữa 2 user profile. Graph có hàng tỉ node — BFS một chiều quá chậm. Bidirectional BFS gặp nhau ở giữa, thực tế chỉ cần explore vài nghìn node mỗi hướng. LinkedIn dùng variation này cho "How are you connected?" feature.

DOM tree traversal: document.querySelectorAll trong browser thực hiện BFS-like traversal qua DOM tree. querySelector trả về node đầu tiên theo BFS order — node gần root nhất match selector.

Network packet broadcast với TTL: mỗi router giảm TTL (Time To Live) trước khi forward packet. TTL = max BFS depth — ngăn packet loop vô tận trên graph có cycle. Packet bị drop khi TTL về 0, tức là đã đi qua nhiều hơn TTL hop kể từ nguồn.

Kubernetes pod scheduling: khi scheduling pod lên cluster node, scheduler dùng BFS-like traversal qua resource topology để tìm node gần nhất đáp ứng resource requirement — cùng rack (1 hop) ưu tiên hơn cùng zone (2 hop), ưu tiên hơn cross-region (3 hop).

11. Deep Dive

12. Tóm tắt

• BFS dùng queue FIFO, duyệt vertex theo từng level từ gần đến xa — đảm bảo vertex được visit lần đầu là qua shortest path.
• Shortest path chỉ đúng trên unweighted graph (mọi cạnh weight = 1). Weighted graph cần Dijkstra.
• Complexity O(V + E) time, O(V) space — mỗi vertex enqueue đúng một lần, mỗi edge kiểm tra đúng một lần.
• Mark visited khi PUSH, không phải khi POP — tránh enqueue cùng vertex nhiều lần, giữ đúng O(V + E).
• Level tracking pattern: snapshot size trước vòng inner để xử lý từng level riêng biệt.
• Multi-source BFS: push tất cả nguồn vào queue ban đầu, chạy một lần BFS — O(V + E) không quan tâm số nguồn.
• Bidirectional BFS: hai BFS gặp nhau ở giữa, giảm từ O(b^d) xuống O(b^(d/2)) — mạnh cho large graph.
• Ứng dụng: web crawler, 6-degree separation, DOM traversal, network TTL, scheduler topology-aware.

13. Tự kiểm tra

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