Đồ thị & duyệt (BFS/DFS)

Tới giờ dữ liệu của mèo con là dãy (mảng, danh sách) hoặc cây. Nhưng rất nhiều thứ trong đời là một mạng lưới quan hệ: bạn bè trên mạng xã hội, các ga tàu nối nhau, những trang web trỏ link qua lại. Cấu trúc cho những thứ đó là đồ thị (graph).

Đồ thị gồm các đỉnh (vertex/node - như mỗi người, mỗi ga) và các cạnh (edge - mối nối giữa hai đỉnh). Cây ở bài trước thật ra chỉ là một đồ thị đặc biệt (có gốc, không chu trình); đồ thị thì tự do hơn nhiều - cạnh nối tuỳ ý, có thể có vòng.

• ▸Đồ thị = đỉnh (vertex) + cạnh (edge), mô hình hoá mạng lưới quan hệ.
• ▸Ví dụ: mạng xã hội, bản đồ giao thông, web, mạng máy tính.
• ▸Cây là đồ thị đặc biệt (có gốc, không chu trình); đồ thị tổng quát hơn.

Có hai cách quen thuộc, và chúng đánh đổi bộ nhớ khác nhau. Danh sách kề (adjacency list): mỗi đỉnh giữ một danh sách các đỉnh kề - đúng những viên gạch ở bài Mảng & danh sách liên kết. Cách này gọn cho đồ thị thưa (ít cạnh), tốn cỡ O(V + E) bộ nhớ.

Ma trận kề (adjacency matrix): một mảng 2 chiều n × n nằm liền kề trong RAM, ô [i][j] bằng 1 nếu có cạnh giữa đỉnh i và j. Hỏi “có cạnh không” thì tức thì O(1), nhưng tốn O(V²) bộ nhớ kể cả khi rất ít cạnh. (Cách một mảng nằm liền kề trong bộ nhớ ra sao là chuyện của bài Bộ nhớ & RAM ở khoá Máy tính hoạt động thế nào.)

• ▸Danh sách kề: mỗi đỉnh một danh sách hàng xóm; O(V + E) bộ nhớ, hợp đồ thị thưa.
• ▸Ma trận kề: mảng 2 chiều n×n; kiểm tra cạnh O(1) nhưng tốn O(V²) bộ nhớ.
• ▸Chọn cách lưu là chọn đánh đổi giữa bộ nhớ và tốc độ kiểm tra cạnh.

Để “đi thăm” mọi đỉnh từ một điểm xuất phát, có hai lối. BFS (Breadth-First Search - duyệt theo chiều rộng) dùng hàng đợi, lan ra theo từng lớp. DFS (Depth-First Search - duyệt theo chiều sâu) dùng ngăn xếp, đâm sâu một nhánh rồi quay lui. Cả hai đều mượn đúng hai công cụ ở bài Ngăn xếp & hàng đợi, cộng một tập đã thăm (chính là một bảng băm dạng set) để khỏi đi lại:

const dothi: Record<string, string[]> = {
  A: ['B', 'C'], B: ['A', 'D', 'E'], C: ['A', 'F'],
  D: ['B'], E: ['B', 'F'], F: ['C', 'E', 'G'], G: ['F'],
};

function bfs(g: Record<string, string[]>, start: string): string[] {
  const thuTu: string[] = [];
  const seen = new Set([start]);
  const queue = [start];               // HANG DOI (FIFO)
  while (queue.length) {
    const cur = queue.shift()!;        // lay o DAU
    thuTu.push(cur);
    for (const nb of g[cur]) if (!seen.has(nb)) { seen.add(nb); queue.push(nb); }
  }
  return thuTu;
}

function dfs(g: Record<string, string[]>, start: string): string[] {
  const thuTu: string[] = [];
  const seen = new Set([start]);
  const stack = [start];               // NGAN XEP (LIFO)
  while (stack.length) {
    const cur = stack.pop()!;          // lay o CUOI
    thuTu.push(cur);
    for (const nb of [...g[cur]].reverse()) if (!seen.has(nb)) { seen.add(nb); stack.push(nb); }
  }
  return thuTu;
}

console.log(bfs(dothi, 'A').join(' '));
console.log(dfs(dothi, 'A').join(' '));

A B C D E F G
A B D E F G C

Hai hàm giống hệt nhau, chỉ khác một dòng: lấy phần tử ở đầu (hàng đợi) hay ở cuối (ngăn xếp). Vậy mà cho hai thứ tự đi rất khác nhau.

• ▸BFS = hàng đợi (lấy ở đầu) → lan theo lớp; DFS = ngăn xếp (lấy ở cuối) → đâm sâu.
• ▸Tập “đã thăm” (hash set) tránh đi lại đỉnh cũ, cần khi đồ thị có chu trình.
• ▸Đổi cấu trúc lưu “biên giới” là đổi luôn kiểu duyệt.

Chọn BFS hay DFS, bấm Tiếp → hoặc Tự chạy, và để ý hàng đợi/ngăn xếp ở dưới cùng đồ thị tô màu phía trên: cùng xuất phát từ A nhưng hai cách lan đi rất khác:

• ▸BFS thăm A, rồi mọi hàng xóm của A, rồi hàng xóm của họ - theo lớp.
• ▸DFS lao theo một nhánh tới tận cùng rồi mới quay lại nhánh khác.
• ▸Ô tô màu coral = đang thăm, xanh = đã xong, viền hổ phách = đang chờ trong biên giới.

Cả BFS lẫn DFS đều thăm mỗi đỉnh một lần và đi qua mỗi cạnh một lần, nên chi phí là O(V + E) (V đỉnh, E cạnh) - rất hiệu quả. Khác nhau là ở thứ tự, và thứ tự đó quyết định bài toán nào hợp cách nào.

• ▸Cả hai: O(V + E) - mỗi đỉnh và mỗi cạnh xử lý một lần.
• ▸BFS: đường ngắn nhất (theo số cạnh), lan đều - hợp “ít trạm nhất”.
• ▸DFS: dò sâu, phát hiện chu trình, sắp thứ tự phụ thuộc (topological sort).

Đồ thị khép lại bộ đồ nghề cấu trúc dữ liệu của mèo con. Đẹp nhất: BFS và DFS không phải phép màu mới - chúng chỉ là hàng đợi và ngăn xếp (bài 3) cộng một hash set (bài 6), áp lên một mạng lưới. Mọi mảnh ghép cả khoá nối vào nhau ở đây.