Cơ bản: đồ thị, danh sách kề, mảng đã thăm

1. Đồ thị là gì

Một đồ thị (graph) gồm hai thứ: một tập đỉnh (vertex) và một tập cạnh (edge) nối các đỉnh với nhau. Hết. Không có gì hơn.

Cái làm đồ thị hữu ích là nó mô tả được rất nhiều thứ: bản đồ đường đi (đỉnh là thành phố, cạnh là đường), mạng bạn bè (đỉnh là người, cạnh là quan hệ bạn bè), bàn cờ (đỉnh là một thế cờ, cạnh là một nước đi), hay một lưới ô vuông trong bài LeetCode.

Đồ thị trên là vô hướng: cạnh giữa 2 và 4 cho phép đi cả hai chiều. Nếu cạnh chỉ đi được một chiều thì ta có đồ thị có hướng — các em sẽ gặp ở bài LeetCode 207.

2. Danh sách kề

Máy tính không nhìn được hình vẽ. Ta phải nói cho nó biết đỉnh nào nối với đỉnh nào. Cách dùng phổ biến nhất, và là cách dùng trong toàn bộ trang này, là danh sách kề (adjacency list): với mỗi đỉnh u, ta lưu một danh sách các đỉnh kề với nó.

Đọc đồ thị từ bàn phím vào danh sách kề:

int n, m;                       // số đỉnh, số cạnh
vector<vector<int>> ke;         // ke[u] = danh sách các đỉnh kề với u

int main() {
    cin >> n >> m;
    ke.assign(n + 1, {});       // đánh số đỉnh từ 1 đến n
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        ke[u].push_back(v);     // đồ thị VÔ HƯỚNG:
        ke[v].push_back(u);     // phải thêm cả hai chiều
    }
}

n, m = map(int, input().split())
ke = [[] for _ in range(n + 1)]   # đánh số đỉnh từ 1 đến n

for _ in range(m):
    u, v = map(int, input().split())
    ke[u].append(v)               # đồ thị VÔ HƯỚNG:
    ke[v].append(u)               # phải thêm cả hai chiều

Còn một cách nữa là ma trận kề: keNhau[u][v] = 1 nếu u nối với v. Cách này tốn O(n²) bộ nhớ nên chỉ dùng khi n nhỏ, nhưng đề LeetCode thỉnh thoảng cho sẵn dữ liệu ở dạng đó (bài 547).

3. Ngăn xếp và hàng đợi

Cả DFS và BFS đều cần một chỗ để “cất tạm” những đỉnh đã biết nhưng chưa xử lý. Khác biệt duy nhất giữa hai thuật toán nằm ở việc chọn cấu trúc nào để cất.

• Ngăn xếp (stack): lấy ra phần tử mới nhất vừa cất vào. Như chồng sách — lấy quyển trên cùng. Trong C++ là stack, hoặc chỉ cần vector với push_back / pop_back.
• Hàng đợi (queue): lấy ra phần tử cũ nhất. Như xếp hàng mua vé — ai đến trước đi trước. Trong C++ là queue, trong Python là collections.deque với append / popleft.

4. Mảng đã thăm — thứ không được phép quên

Hãy nhìn lại đồ thị mẫu và đi thử bằng tay: 1 → 2 → 4 → 7 → 5 → 2 → 4 → 7 → 5 → 2 → …

Các đỉnh 2, 4, 7, 5 tạo thành một chu trình. Không có gì trong “khung duyệt” ngăn ta đi vòng quanh nó mãi mãi. Chương trình sẽ chạy vô hạn, hoặc tràn ngăn xếp nếu viết bằng đệ quy.

Cách chữa là một mảng daTham (visited): mỗi đỉnh được đánh dấu một lần, và ta không bao giờ xử lý một đỉnh đã đánh dấu lần thứ hai. Nhờ nó, mỗi đỉnh được thăm đúng một lần và mỗi cạnh được xét đúng hai lần (một lần từ mỗi đầu) — đó là lý do cả hai thuật toán chạy trong O(V + E).

5. Khung chung của cả hai thuật toán

Đây là điều mình muốn các em nhớ nhất từ trang này. DFS và BFS không phải hai thuật toán khác nhau cần học riêng. Chúng là một khung duyệt, khác nhau ở đúng một dòng:

// KHUNG CHUNG của cả DFS và BFS
hangCho.dua_vao(dinhBatDau);

while (hangCho không rỗng) {
    u = hangCho.lay_ra();        // ← CHỖ DUY NHẤT hai thuật toán khác nhau
    danhDau(u);
    xuLy(u);
    for (v : ke[u])
        if (!daTham[v])
            hangCho.dua_vao(v);
}

# KHUNG CHUNG của cả DFS và BFS
hangCho.dua_vao(dinhBatDau)

while hangCho:
    u = hangCho.lay_ra()         # ← CHỖ DUY NHẤT hai thuật toán khác nhau
    danhDau(u)
    xuLy(u)
    for v in ke[u]:
        if not daTham[v]:
            hangCho.dua_vao(v)

Nếu hangCho là ngăn xếp, ta được DFS. Nếu là hàng đợi, ta được BFS. Thật sự chỉ có vậy.

6. Lưới cũng là đồ thị

Rất nhiều bài LeetCode không nói chữ “đồ thị” nào, mà cho một bảng ô vuông. Đừng để bị lừa: đó là đồ thị, chỉ là danh sách kề được giấu đi.

Quy tắc chuyển đổi:

Vì ke[u] tính được tại chỗ, code duyệt lưới thường ngắn hơn code duyệt đồ thị. Bốn hướng viết gọn như sau:

int dr[] = {-1, 0, 1, 0};   // lên, phải, xuống, trái
int dc[] = {0, 1, 0, -1};

for (int k = 0; k < 4; k++) {
  int nr = r + dr[k], nc = c + dc[k];
  if (nr < 0 || nc < 0 || nr >= n || nc >= m) continue;  // ra ngoài lưới
  // ... xử lý ô (nr, nc)
}

for dr, dc in ((-1, 0), (0, 1), (1, 0), (0, -1)):   # lên, phải, xuống, trái
  nr, nc = r + dr, c + dc
  if not (0 <= nr < n and 0 <= nc < m):          # ra ngoài lưới
      continue
  # ... xử lý ô (nr, nc)

Xong phần nền. Giờ ta vào thuật toán thật.