Lý Thuyết Đồ Thị Cơ Bản: Duyệt BFS & DFS

1. Bản chất đồ thị & các phương pháp biểu diễn

Đồ thị $G = (V, E)$ là cấu trúc toán học biểu diễn tập hợp các đỉnh (Vertices — $V$) và các cạnh nối giữa chúng (Edges — $E$). Đồ thị có thể là vô hướng (Undirected) hoặc có hướng (Directed), có trọng số hoặc không có trọng số.

1.1. Ma trận kề (adjacency matrix)

• Mảng 2 chiều int adj[N][N]: adj[u][v] = 1 nếu có cạnh nối giữa $u$ và $v$.
• Ưu điểm: Kiểm tra cạnh $(u, v)$ trong $\mathcal{O}(1)$.
• Nhược điểm: Tốn $\mathcal{O}(N^2)$ bộ nhớ. Khi $N = 10^5$, ma trận cần $40\text{GB}$ RAM $\implies$ Sập bộ nhớ ngay lập tức (MLE). Chỉ dùng khi $N \le 1000$.

1.2. Danh sách kề (adjacency list — Chuẩn mực thi đấu)

• Sử dụng mảng các vector vector<int> adj[N + 1]: adj[u] chứa toàn bộ các đỉnh kề trực tiếp với $u$.

• Bộ nhớ: Đúng $\mathcal{O}(V + E)$, cực kỳ tiết kiệm và tối ưu cho đồ thị thưa trong lập trình thi đấu ($N, M \le 2 \cdot 10^5$).

• Duyệt đỉnh kề: for (int v : adj[u]) tốn thời gian tỷ lệ thuận với bậc của đỉnh $\mathcal{O}(\text{deg}(u))$.

2. Hai chiến lược duyệt đồ thị kinh điển: BFS vs DFS

2.1. Tìm kiếm theo chiều rộng (breadth-first search — BFS)

• Sử dụng Hàng đợi (Queue), lan tỏa theo từng tầng bán kính $d = 0, 1, 2, \dots$ tính từ đỉnh nguồn $S$.
• Đặc tính vàng: Tìm đường đi có ít cạnh nhất (ngắn nhất) trên đồ thị không trọng số.

2.2. Tìm kiếm theo chiều sâu (depth-first search — DFS)

• Sử dụng Đệ quy (hoặc Stack), đi sâu hết mức có thể trên một nhánh cho đến khi gặp ngõ cụt thì quay lui (Backtracking).
• Đặc tính vàng: Cực kỳ hiệu quả để đếm thành phần liên thông, phát hiện chu trình, kiểm tra tính liên thông, định hướng cây DFS.

3. Ứng dụng: Đếm số thành phần liên thông & kiểm tra chu trình

• Thuật toán đếm thành phần liên thông: Duyệt qua mọi đỉnh $i \in [1, N]$. Nếu đỉnh $i$ chưa được thăm (!visited[i]), tăng biến đếm số thành phần liên thông components++ và gọi DFS(i) để loang thăm toàn bộ các đỉnh thuộc cùng thành phần.
• Phát hiện chu trình trên đồ thị vô hướng bằng DFS: Khi duyệt từ $u$ sang đỉnh kề $v$, nếu $v$ đã được thăm (visited[v] == true) và v != parent[u], ta khẳng định đồ thị CÓ CHU TRÌNH!

4. Các bẫy lỗi lập trình kinh điển (bug traps)

1. Bẫy thêm cạnh đồ thị vô hướng chỉ thêm 1 chiều: * Với đồ thị vô hướng, cạnh giữa $u$ và $v$ phải thêm cả 2 chiều: adj[u].push_back(v); adj[v].push_back(u);. Quên thêm chiều thứ hai làm đồ thị biến thành đồ thị có hướng sai hoàn toàn.
2. Bẫy tràn ngăn xếp đệ quy (Stack Overflow) khi DFS đồ thị sâu: * Nếu đồ thị là một đường thẳng $N = 2 \cdot 10^5$ đỉnh, hàm đệ quy DFS sẽ gọi sâu $2 \cdot 10^5$ tầng, vượt quá giới hạn ngăn xếp (Call Stack) của một số hệ điều hành và gây Runtime Error.
3. Bẫy cạnh lặp và khuyên (Multiple Edges & Self-loops): * Đề bài có thể cho nhiều cạnh nối giữa cùng một cặp đỉnh $(u, v)$ hoặc cạnh tự nối $u \to u$. Cần kiểm tra hoặc xử lý cẩn thận nếu thuật toán yêu cầu tính toán bậc hoặc trọng số tối thiểu.

5. Mẫu cài đặt chuẩn thi đấu (competitive templates)

Mẫu 1: DFS đếm số thành phần liên thông và tìm kích thước từng thành phần

⚠️ Lưu ý về Stack Overflow: Hàm DFS đệ quy dưới đây có thể gây tràn ngăn xếp hệ thống (Segmentation Fault) khi đồ thị có dạng đường thẳng $N = 2 \times 10^5$ đỉnh (độ sâu đệ quy lên tới $N$ tầng). Trong thi đấu thực tế, nên dùng DFS bằng std::stack tường minh hoặc thiết lập ulimit -s unlimited (Linux) trước khi chạy. Mẫu đệ quy được giữ lại ở đây vì tính trực quan sư phạm.

#include <bits/stdc++.h>
using namespace std;

int n, m;
vector<vector<int>> adj;

vector<bool> visited;

int dfs(int u) {
    visited[u] = true;
    int comp_size = 1;
    for (int v : adj[u]) {
        if (!visited[v]) {
            comp_size += dfs(v);
        }
    }
    return comp_size;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if (!(cin >> n >> m)) return 0;

    if (n <= 0) return 0;

    adj.assign(n + 1, vector<int>());
    visited.assign(n + 1, false);

    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;

        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    int component_count = 0;
    vector<int> component_sizes;

    for (int i = 1; i <= n; ++i) {
        if (!visited[i]) {
            component_count++;
            int sz = dfs(i);
            component_sizes.push_back(sz);
        }
    }

    cout << component_count << "\n";
    for (int i = 0; i < (int)component_sizes.size(); ++i) {
        cout << component_sizes[i] << (i + 1 == (int)component_sizes.size() ? "" : " ");
    }
    cout << "\n";

    return 0;
}

Mẫu 2: Phát hiện chu trình trên đồ thị vô hướng bằng DFS

#include <bits/stdc++.h>
using namespace std;

int n, m;
vector<vector<int>> adj;

vector<bool> visited;

bool has_cycle = false;

void dfs_cycle(int u, int p) {
    visited[u] = true;
    for (int v : adj[u]) {
        if (!visited[v]) {
            dfs_cycle(v, u);
        } else if (v != p) {
            has_cycle = true; // Gặp lại đỉnh đã thăm khác cha -> Chu trình!

        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if (!(cin >> n >> m)) return 0;

    if (n <= 0) return 0;

    adj.assign(n + 1, vector<int>());
    visited.assign(n + 1, false);

    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;

        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    for (int i = 1; i <= n; ++i) {
        if (!visited[i]) {
            dfs_cycle(i, 0);
        }
    }

    if (has_cycle) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }

    return 0;
}