BFS — Breadth-First Search và unweighted shortest path

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.

1. Init: queue = [start], visited = {start}, distance[start] = 0.
2. While queue not empty:
   a. v = queue.poll()           -- lay vertex dau hang
   b. For each neighbor u of v:
      If u not visited:
         mark visited
         distance[u] = distance[v] + 1
         parent[u] = v            -- ghi lai de reconstruct path
         queue.offer(u)           -- them vao cuoi hang
3. Output: distance[] (-1 neu unreachable), parent[] de reconstruct.

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

3. Code Java — BFS đầy đủ

import java.util.*;

public class BFS {

    // Returns distance[] from start to every vertex.
    // distance[v] = -1 means unreachable.
    public static int[] bfs(List<List<Integer>> adj, int start) {
        int n = adj.size();
        int[] distance = new int[n];
        Arrays.fill(distance, -1);

        Queue<Integer> queue = new ArrayDeque<>();
        queue.offer(start);
        distance[start] = 0;          // mark visited by setting distance >= 0

        while (!queue.isEmpty()) {
            int v = queue.poll();
            for (int u : adj.get(v)) {
                if (distance[u] == -1) {  // not visited yet
                    distance[u] = distance[v] + 1;
                    queue.offer(u);
                }
            }
        }
        return distance;
    }

    // Returns shortest path from start to target as list of vertices.
    // Returns empty list if unreachable.
    public static List<Integer> shortestPath(List<List<Integer>> adj,
                                              int start, int target) {
        int n = adj.size();
        int[] parent = new int[n];
        Arrays.fill(parent, -1);
        boolean[] visited = new boolean[n];

        Queue<Integer> queue = new ArrayDeque<>();
        queue.offer(start);
        visited[start] = true;         // mark BEFORE push, not after poll

        while (!queue.isEmpty()) {
            int v = queue.poll();
            if (v == target) {
                // Reconstruct path by walking parent[] backwards
                List<Integer> path = new ArrayList<>();
                for (int cur = target; cur != -1; cur = parent[cur]) {
                    path.add(cur);
                }
                Collections.reverse(path);
                return path;
            }
            for (int u : adj.get(v)) {
                if (!visited[u]) {
                    visited[u] = true;     // mark visited when pushing
                    parent[u] = v;
                    queue.offer(u);
                }
            }
        }
        return List.of();  // target unreachable
    }
}

3.1 Trace ví dụ — graph 6 vertex

Graph: 0-1, 0-2, 1-3, 1-4, 2-4, 3-5. BFS từ vertex 0.

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

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

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 poll 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 distance[] và visited[] 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.

public static void bfsByLevel(List<List<Integer>> adj, int start) {
    Queue<Integer> queue = new ArrayDeque<>();
    queue.offer(start);
    Set<Integer> visited = new HashSet<>();
    visited.add(start);
    int level = 0;

    while (!queue.isEmpty()) {
        int size = queue.size();  // snapshot so luong node o level hien tai
        for (int i = 0; i < size; i++) {
            int v = queue.poll();
            // process v at level 'level' here
            for (int u : adj.get(v)) {
                if (visited.add(u)) {  // add() tra false neu da ton tai
                    queue.offer(u);
                }
            }
        }
        level++;
    }
}

Key pattern: snapshot queue.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.

7. Pitfall tổng hợp

Pitfall 1 — Mark visited khi POP thay khi PUSH

// BUG: mark visited when polling, not when offering
while (!queue.isEmpty()) {
    int v = queue.poll();
    visited[v] = true;            // too late -- already in queue multiple times
    for (int u : adj.get(v)) {
        if (!visited[u]) {
            queue.offer(u);       // u co the duoc add nhieu lan truoc khi visited
        }
    }
}

Nếu vertex u có 3 neighbor đều chưa visited, u sẽ bị enqueue 3 lần. Với dense graph điều này gây exponential blowup — queue phình to phi tuyến.

// CORRECT: mark visited BEFORE pushing
for (int u : adj.get(v)) {
    if (!visited[u]) {
        visited[u] = true;    // mark truoc khi push
        queue.offer(u);
    }
}

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 chi dem canh, khong dem weight:
// BFS tim A->B = 1 canh, tra ve path [A, B], "distance" = 1
// Nhung tong weight = 5
// Path A->C->B co 2 canh nhung tong weight = 2 -- ngan hon!
// BFS bo qua path nay vi "nhieu canh hon"

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: dung Stack thay Queue
Deque<Integer> stack = new ArrayDeque<>();
stack.push(start);   // push = addFirst

while (!stack.isEmpty()) {
    int v = stack.pop();   // pop = pollFirst -- LIFO
    for (int u : adj.get(v)) {
        if (!visited[u]) {
            visited[u] = true;
            stack.push(u);
        }
    }
}
// Day la DFS, khong phai BFS -- khong guarantee shortest path

Thay stack.push/pop bằng queue.offer/poll — 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.

public static int[] multiSourceBfs(List<List<Integer>> adj,
                                    List<Integer> sources) {
    int n = adj.size();
    int[] distance = new int[n];
    Arrays.fill(distance, -1);

    Queue<Integer> queue = new ArrayDeque<>();
    for (int s : sources) {
        queue.offer(s);
        distance[s] = 0;           // moi source co distance = 0
    }

    while (!queue.isEmpty()) {
        int v = queue.poll();
        for (int u : adj.get(v)) {
            if (distance[u] == -1) {
                distance[u] = distance[v] + 1;
                queue.offer(u);
            }
        }
    }
    return distance;   // distance[v] = nearest source distance
}

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.

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.

// Sketch -- bidirectional BFS
public static int bidirectionalBfs(List<List<Integer>> adj, int s, int t) {
    if (s == t) return 0;
    Set<Integer> visitedS = new HashSet<>();
    Set<Integer> visitedT = new HashSet<>();
    Queue<Integer> queueS = new ArrayDeque<>();
    Queue<Integer> queueT = new ArrayDeque<>();
    Map<Integer, Integer> distS = new HashMap<>();
    Map<Integer, Integer> distT = new HashMap<>();

    queueS.offer(s); distS.put(s, 0); visitedS.add(s);
    queueT.offer(t); distT.put(t, 0); visitedT.add(t);

    while (!queueS.isEmpty() || !queueT.isEmpty()) {
        // Expand the smaller frontier for balance
        int result = expand(adj, queueS, visitedS, distS, visitedT, distT);
        if (result != -1) return result;
        result = expand(adj, queueT, visitedT, distT, visitedS, distS);
        if (result != -1) return result;
    }
    return -1;  // unreachable
}

private static int expand(List<List<Integer>> adj,
                           Queue<Integer> queue,
                           Set<Integer> visited, Map<Integer, Integer> dist,
                           Set<Integer> otherVisited, Map<Integer, Integer> otherDist) {
    if (queue.isEmpty()) return -1;
    int v = queue.poll();
    for (int u : adj.get(v)) {
        if (!visited.contains(u)) {
            visited.add(u);
            dist.put(u, dist.get(v) + 1);
            queue.offer(u);
            if (otherVisited.contains(u)) {
                return dist.get(u) + otherDist.get(u);  // meeting point found
            }
        }
    }
    return -1;
}

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

Queue<Integer> queue = new ArrayDeque<>();
queue.offer(root);
visited.add(root);

while (!queue.isEmpty()) {
  int size = queue.size(); // snapshot -- so node o level nay
  List<Integer> level = new ArrayList<>();
  for (int i = 0; i < size; i++) {
      int v = queue.poll();
      level.add(v);
      for (int u : adj.get(v)) {
          if (visited.add(u)) {
              queue.offer(u);
          }
      }
  }
  result.add(level); // moi level la 1 list rieng
}

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