Phát hiện chu trình trong đồ thị bằng Topological Sort (C++)

Topological Sort chỉ tồn tại trên DAG. Do đó, **thử thực hiện Topological Sort** là một cách tự nhiên để kiểm tra đồ thị có chu trình hay không.

Phương pháp 1: Kahn's Algorithm (BFS) - Khuyên dùng

Nếu sau khi xử lý xong, số đỉnh trong kết quả < V → có chu trình.

bool hasCycleKahn(int V, const vector>& adj) {
    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();
        cnt++;
        for (int v : adj[u])
            if (--indeg[v] == 0) q.push(v);
    }
    return cnt != V; // true = có chu trình
}

Phương pháp 2: DFS với màu (Color) - Phát hiện sớm

Duyệt DFS, đánh dấu: 0=WHITE (chưa thăm), 1=GRAY (đang trong stack đệ quy), 2=BLACK (hoàn tất). Gặp cạnh u→v với color[v]==GRAY → **Back Edge → Có chu trình**.

bool hasCycleDFS(int V, const vector>& adj) {
    vector color(V, 0);
    function dfs = [&](int u) {
        color[u] = 1; // GRAY
        for (int v : adj[u]) {
            if (color[v] == 0) {
                if (dfs(v)) return true;
            } else if (color[v] == 1) {
                return true; // Back edge -> cycle
            }
        }
        color[u] = 2; // BLACK
        return false;
    };
    
    for (int i = 0; i < V; ++i)
        if (color[i] == 0 && dfs(i)) return true;
    return false;
}

Phương pháp 3: Union-Find (Chỉ cho đồ thị VÔ HƯỚNG)

Không áp dụng cho đồ thị có hướng (directed).

Chương trình hoàn chỉnh (So sánh 2 phương pháp)

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

bool hasCycleKahn(int V, const vector>& adj) {
    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();
        cnt++;
        for (int v : adj[u])
            if (--indeg[v] == 0) q.push(v);
    }
    return cnt != V;
}

bool hasCycleDFS(int V, const vector>& adj) {
    vector color(V, 0);
    function dfs = [&](int u) {
        color[u] = 1;
        for (int v : adj[u]) {
            if (color[v] == 0) {
                if (dfs(v)) return true;
            } else if (color[v] == 1) {
                return true;
            }
        }
        color[u] = 2;
        return false;
    };
    
    for (int i = 0; i < V; ++i)
        if (color[i] == 0 && dfs(i)) return true;
    return false;
}

void testCase(const string& name, int V, const vector>& edges) {
    vector> adj(V);
    for (auto [u, v] : edges) adj[u].push_back(v);
    
    cout << name << ":\n";
    cout << "  Kahn:  " << (hasCycleKahn(V, adj) ? "CO CHU TRINH" : "KHONG CO CHU TRINH (DAG)") << '\n';
    cout << "  DFS:   " << (hasCycleDFS(V, adj) ? "CO CHU TRINH" : "KHONG CO CHU TRINH (DAG)") << '\n';
    cout << '\n';
}

int main() {
    // Test 1: DAG đơn giản
    testCase("Test 1: DAG", 4, {{0,1}, {0,2}, {1,3}, {2,3}});
    
    // Test 2: Chu trình tự thân (self-loop)
    testCase("Test 2: Self-loop", 3, {{0,1}, {1,2}, {2,2}});
    
    // Test 3: Chu trình 3 đỉnh
    testCase("Test 3: Cycle 0-1-2-0", 3, {{0,1}, {1,2}, {2,0}});
    
    // Test 4: Chu trình lớn hơn
    testCase("Test 4: Cycle 1-2-3-1", 5, {{0,1}, {1,2}, {2,3}, {3,1}, {3,4}});
    
    // Test 5: Đồ thị không liên thông, 1 thành phần có chu trình
    testCase("Test 5: Disconnected + cycle", 6, {{0,1}, {1,2}, {3,4}, {4,5}, {5,3}});
    
    // Test 6: Ví dụ từ bài gốc (ma trận kề)
    cout << "Test 6: Vi du ma tran ke 5x5 (0->1, 1->2, 2->3, 3->4, 4->0):\n";
    vector> adj6(5);
    adj6[0].push_back(1);
    adj6[1].push_back(2);
    adj6[2].push_back(3);
    adj6[3].push_back(4);
    adj6[4].push_back(0); // Cycle!
    cout << "  Kahn: " << (hasCycleKahn(5, adj6) ? "CO CHU TRINH" : "DAG") << '\n';
    cout << "  DFS:  " << (hasCycleDFS(5, adj6) ? "CO CHU TRINH" : "DAG") << '\n';
    
    return 0;
}

Kết quả

Test 1: DAG:
  Kahn:  KHONG CO CHU TRINH (DAG)
  DFS:   KHONG CO CHU TRINH (DAG)

Test 2: Self-loop:
  Kahn:  CO CHU TRINH
  DFS:   CO CHU TRINH

Test 3: Cycle 0-1-2-0:
  Kahn:  CO CHU TRINH
  DFS:   CO CHU TRINH

Test 4: Cycle 1-2-3-1:
  Kahn:  CO CHU TRINH
  DFS:   CO CHU TRINH

Test 5: Disconnected + cycle:
  Kahn:  CO CHU TRINH
  DFS:   CO CHU TRINH

Test 6: Vi du ma tran ke 5x5 (0->1, 1->2, 2->3, 3->4, 4->0):
  Kahn: CO CHU TRINH
  DFS:  CO CHU TRINH

So sánh chi tiết

Mở rộng: Tìm chu trình cụ thể (không chỉ yes/no)

DFS: lưu parent[], khi gặp back edge u→v, truy vết từ u lên v qua parent.

vector findCycle(int V, const vector>& adj) {
    vector color(V, 0), parent(V, -1), cycle;
    function dfs = [&](int u) {
        color[u] = 1;
        for (int v : adj[u]) {
            if (color[v] == 0) {
                parent[v] = u;
                if (dfs(v)) return true;
            } else if (color[v] == 1) {
                // Tìm thấy cycle: v -> ... -> u -> v
                cycle.push_back(v);
                for (int x = u; x != v; x = parent[x])
                    cycle.push_back(x);
                cycle.push_back(v);
                reverse(cycle.begin(), cycle.end());
                return true;
            }
        }
        color[u] = 2;
        return false;
    };
    for (int i = 0; i < V; ++i)
        if (color[i] == 0 && dfs(i)) break;
    return cycle;
}

Phát hiện chu trình là bài toán cốt lõi, ứng dụng trong: deadlock detection, dependency resolution, compiler optimization, model checking.