Lý Thuyết Đồ Thị Cơ Bản & Nâng Cao

1. Khái niệm & biểu diễn đồ thị trong lập trình thi đấu

Lý thuyết đồ thị (Graph Theory) là mô hình trừu tượng mô tả mối quan hệ (các cạnh $E$) giữa các đối tượng (các đỉnh $V$).

Các phương pháp biểu diễn đồ thị chuẩn:

• Danh sách kề (vector<vector<int>> adj): Tiết kiệm bộ nhớ $\mathcal{O}(V + E)$, duyệt các đỉnh kề nhanh nhất $\implies$ Chuẩn thi đấu bắt buộc.
• Ma trận kề (vector<vector<int>> matrix): Tốn bộ nhớ $\mathcal{O}(V^2)$, chỉ dùng khi $V \le 1000$.
• Danh sách cạnh (vector<vector<int>> edges): Dùng trong các thuật toán cây khung nhỏ nhất (Kruskal, Bellman-Ford).

2. Hai thuật toán duyệt đồ thị cốt lõi: BFS & DFS

2.1. Tìm kiếm theo chiều sâu (Depth-First Search — DFS)

• Duyệt đi sâu vào từng nhánh theo cơ chế đệ quy (Stack ngầm định).
• Ứng dụng: Đếm thành phần liên thông, phát hiện chu trình (Cycle Detection), sắp xếp Tô-pô (Topological Sort), kiểm tra đồ thị hai phía (Bipartite Graph).

void dfs(int u, const vector<vector<int>> &adj, vector<bool> &visited) {
    visited[u] = true;
    for (int v : adj[u]) {
        if (!visited[v]) dfs(v, adj, visited);
    }
}

2.2. Tìm kiếm theo chiều rộng (Breadth-First Search — BFS)

• Duyệt theo từng lớp khoảng cách lan tỏa bằng Hàng đợi (queue<int>).
• Tính chất vàng: BFS luôn tìm ra đường đi ngắn nhất (ít cạnh nhất) trên đồ thị không có trọng số hoặc đồ thị lưới 2D.

vector<int> bfs_shortest_path(int start_node, int n, const vector<vector<int>> &adj) {
    vector<int> dist(n + 1, -1);
    queue<int> q;

    dist[start_node] = 0;
    q.push(start_node);

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        for (int v : adj[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
    return dist;
}

3. Thuật toán Dijkstra

Khi các cạnh có trọng số $W_e \ge 0$, ta sử dụng thuật toán Dijkstra kết hợp Hàng đợi ưu tiên (Min-Heap) đạt độ phức tạp $\mathcal{O}((V + E) \log V)$:

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

const long long INF = 1e18;

vector<long long> dijkstra(int start_node, int n, const vector<vector<pair<int, long long>>> &adj) {
    vector<long long> dist(n + 1, INF);
    // Min-heap lưu {khoảng_cách, đỉnh}
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;

    dist[start_node] = 0;
    pq.push({0, start_node});

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();

        if (d > dist[u]) continue; // Bỏ qua trạng thái cũ

        for (auto &edge : adj[u]) {
            int v = edge.first;
            long long w = edge.second;
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

4. Ranh giới áp dụng