Kiểm tra Topological Sort có thể thực hiện được không (DAG) trong C++

Topological Sort (Sắp xếp topo) chỉ tồn tại trên Đồ thị có hướng không chu trình (DAG - Directed Acyclic Graph). Nếu đồ thị có chu trình → không thể topo sort.

Thuật toán Kahn (BFS - Indegree)

1. Tính indegree (số cạnh vào) cho mọi đỉnh.
2. Đưa tất cả đỉnh indegree = 0 vào hàng đợi.
3. Lặp: lấy đỉnh u từ queue, thêm vào kết quả, giảm indegree của các đỉnh kề v. Nếu indegree[v] == 0 → push queue.
4. Nếu số đỉnh trong kết quả < V → có chu trình.

Thuật toán DFS (Stack)

1. DFS, đánh dấu trạng thái: WHITE (chưa thăm), GRAY (đang thăm), BLACK (hoàn tất).
2. Nếu gặp cạnh đến đỉnh GRAY → Back Edge → Có chu trình.
3. Sau khi thăm xong con, push đỉnh vào stack.
4. Đảo ngược stack → thứ tự topo.

Chương trình C++: Cả 2 phương pháp

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

class Graph {
    int V;
    vector> adj;
    
public:
    Graph(int V) : V(V), adj(V) {}
    void addEdge(int u, int v) { adj[u].push_back(v); }
    
    // Kahn's Algorithm (BFS)
    bool topoKahn(vector& result) {
        vector indeg(V, 0);
        for (int u = 0; u < V; ++u)
            for (int v : adj[u]) indeg[v]++;
        
        queue q;
        for (int i = 0; i < V; ++i)
            if (indeg[i] == 0) q.push(i);
        
        int cnt = 0;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            result.push_back(u);
            cnt++;
            for (int v : adj[u]) {
                if (--indeg[v] == 0) q.push(v);
            }
        }
        return cnt == V; // true = DAG, false = có chu trình
    }
    
    // DFS với phát hiện chu trình
    bool topoDFS(vector& result) {
        vector state(V, 0); // 0=WHITE, 1=GRAY, 2=BLACK
        bool hasCycle = false;
        
        function dfs = [&](int u) {
            state[u] = 1; // GRAY
            for (int v : adj[u]) {
                if (state[v] == 0) dfs(v);
                else if (state[v] == 1) hasCycle = true; // Back edge
            }
            state[u] = 2; // BLACK
            result.push_back(u);
        };
        
        for (int i = 0; i < V; ++i)
            if (state[i] == 0) dfs(i);
        
        reverse(result.begin(), result.end());
        return !hasCycle;
    }
};

int main() {
    // Ví dụ 1: DAG
    Graph g1(6);
    g1.addEdge(5, 2); g1.addEdge(5, 0);
    g1.addEdge(4, 0); g1.addEdge(4, 1);
    g1.addEdge(2, 3); g1.addEdge(3, 1);
    
    vector res1;
    if (g1.topoKahn(res1)) {
        cout << "Do thi 1: DAG - Topo Sort (Kahn): ";
        for (int v : res1) cout << v << ' ';
        cout << '\n';
    } else {
        cout << "Do thi 1: CO CHU TRINH\n";
    }
    
    // Ví dụ 2: Có chu trình
    Graph g2(4);
    g2.addEdge(0, 1); g2.addEdge(1, 2); g2.addEdge(2, 3); g2.addEdge(3, 1); // 1->2->3->1
    
    vector res2;
    if (g2.topoKahn(res2)) {
        cout << "Do thi 2: DAG - Topo Sort: ";
        for (int v : res2) cout << v << ' ';
    } else {
        cout << "Do thi 2: CO CHU TRINH (Khong the Topo Sort)\n";
    }
    
    // Test DFS method
    cout << "\n--- DFS Method ---\n";
    vector res3;
    if (g1.topoDFS(res3)) {
        cout << "Do thi 1 (DFS): ";
        for (int v : res3) cout << v << ' ';
    }
    cout << '\n';
    
    return 0;
}

Kết quả

Do thi 1: DAG - Topo Sort (Kahn): 5 4 2 3 1 0
Do thi 2: CO CHU TRINH (Khong the Topo Sort)

--- DFS Method ---
Do thi 1 (DFS): 5 4 2 3 1 0

So sánh 2 phương pháp

Ứng dụng thực tế

• Lịch thi / Lịch học (môn tiên quyết).
• Build system (Make, CMake, Bazel): thứ tự biên dịch module.
• Package manager (npm, pip, cargo): resolve dependency.
• Task scheduling (Airflow, CI/CD pipeline).
• Phân tích deadlock (wait-for graph).

Lưu ý

• DAG có thể có nhiều thứ tự topo hợp lệ.
• Nếu cần thứ tự topo duy nhất → kiểm tra tại mỗi bước queue có đúng 1 phần tử không.
• Đồ thị không liên thông: thuật toán vẫn hoạt động (xử lý từng thành phần).

Topological Sort là bài toán nền tảng, xuất hiện ở khắp nơi trong CS: scheduling, dependency resolution, data serialization.