โปรแกรม C++ ตรวจสอบว่า Graph เป็น DAG หรือไม่

Directed Acyclic Graph (DAG) คือกราฟที่มีทิศทาง (directed) และไม่มีวัฏจักร (cycle) ที่เชื่อมต่อขอบอื่นๆ ขอบของกราฟนี้ไปในทิศทางเดียว นี่คือโปรแกรม C++ ตรวจสอบว่ากราฟเป็น DAG หรือไม่

อัลกอริธึม (Kahn's Algorithm / Topological Sort based)

โค้ดต้นฉบับใช้อัลกอริธึมที่ซับซ้อนและมีบั๊ก (เข้าถึง arr[i].ptr->d เมื่อ ptr == NULL) ด้านล่างคืออัลกอริธึมมาตรฐาน Kahn's Algorithm:

1. คำนวณ indegree ของทุกโหนด
2. Push โหนดที่ indegree = 0 เข้า queue
3. While queue ไม่ว่าง:
   • Pop u, นับ visited++
   • ลด indegree ของเพื่อนบ้าน v ลง 1
   • ถ้า indegree[v] == 0 push v
4. ถ้า visited == จำนวนโหนด → เป็น DAG (ไม่มี cycle) มิฉะนั้นมี cycle

โค้ดตัวอย่าง (แก้ไขและปรับปรุง)

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

bool isDAG(int V, const vector<vector<int>> &adj) {
    vector<int> indegree(V, 0);

    // คำนวณ indegree
    for (int u = 0; u < V; ++u)
        for (int v : adj[u])
            indegree[v]++;

    queue<int> q;
    // Push โหนดที่ไม่มีขอบเข้า
    for (int i = 0; i < V; ++i)
        if (indegree[i] == 0) q.push(i);

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

    return visited == V; // true = DAG, false = มี cycle
}

int main() {
    int V = 4;
    cout << "Number of vertices: " << V << endl;

    // Adjacency list
    vector<vector<int>> adj(V);
    // Edges: 1->0, 3->1, 2->1, 0->3, 4->1 (แต่ V=4 ดังนั้น 4 ไม่มี)
    adj[1].push_back(0);
    adj[3].push_back(1);
    adj[2].push_back(1);
    adj[0].push_back(3);

    // พิมพ์ adjacency list
    for (int i = 0; i < V; ++i) {
        cout << "Adjacency List of " << i << ": ";
        for (int v : adj[i]) cout << v << " ";
        cout << endl;
    }

    cout << "The given graph is 'Directed Acyclic Graph': ";
    if (isDAG(V, adj))
        cout << "yes";
    else
        cout << "no";

    return 0;
}

ผลลัพธ์

Number of vertices: 4
Adjacency List of 0: 3
Adjacency List of 1: 0
Adjacency List of 2: 1
Adjacency List of 3: 1
The given graph is 'Directed Acyclic Graph': yes

การใช้งาน DAG: Task scheduling, dependency resolution, build systems, compiler optimization, version control (Git DAG)