Chương trình C++ kiểm tra đồ thị có phải DAG

DAG (Directed Acyclic Graph) là đồ thị có hướng không chứa chu trình. Kiểm tra DAG thường dùng thuật toán Kahn (BFS loại bỏ đỉnh bậc vào 0) hoặc DFS phát hiện back-edge.

Chương trình dưới dùng phương pháp loại bỏ đỉnh bậc vào 0 (Kahn) trên biểu diễn danh sách kề ngược.

Thuật toán (Kahn)

1. Tính bậc vào (in-degree) của mọi đỉnh.
2. Đưa tất cả đỉnh bậc vào 0 vào hàng đợi.
3. Lặp: lấy đỉnh u từ queue, giảm bậc vào của các đỉnh kề v, nếu bậc vào v thành 0 thì push v.
4. Đếm số đỉnh đã xử lý. Nếu = số đỉnh tổng → DAG, ngược lại có chu trình.

Ví dụ mã (dựa trên code gốc, sửa lỗi logic)

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {
    int V = 4;
    vector<vector<int>> adj(V);
    vector<int> inDegree(V, 0);

    // Thêm cạnh: 1->0, 3->1, 2->1, 0->3, 4->1 (đỉnh 4 không tồn tại nếu V=4, sửa thành 0-based)
    // Sử dụng 0-based indexing
    auto addEdge = [&](int u, int v) {
        adj[u].push_back(v);
        inDegree[v]++;
    };

    addEdge(1, 0);
    addEdge(3, 1);
    addEdge(2, 1);
    addEdge(0, 3);
    // addEdge(4, 1); // bỏ qua vì V=4

    cout << "Danh sách kề:\n";
    for (int i = 0; i < V; ++i) {
        cout << i << ": ";
        for (int v : adj[i]) cout << v << ' ';
        cout << endl;
    }

    // Kahn
    queue<int> q;
    for (int i = 0; i < V; ++i)
        if (inDegree[i] == 0) q.push(i);

    int count = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        count++;
        for (int v : adj[u]) {
            if (--inDegree[v] == 0)
                q.push(v);
        }
    }

    cout << "Đồ thị là DAG: " << (count == V ? "CÓ" : "KHÔNG") << endl;
    return 0;
}

Kết quả

Danh sách kề:
0: 3
1: 0
2: 1
3: 1
Đồ thị là DAG: KHÔNG

Giải thích: Đồ thị có chu trình 0 → 3 → 1 → 0 nên không phải DAG. Code gốc có lỗi logic trong checkDAG, phiên bản trên dùng thuật toán Kahn chuẩn.