C++-এ গ্রাফ DAG (Directed Acyclic Graph) কিনা যাচাই

ডায়রেক্টেড অ্যাসাইক্লিক গ্রাফ (DAG) হলো এমন একটি ডায়রেক্টেড গ্রাফ যাতে কোনো সাইকেল (cycle) নেই। এজগুলো একদিকেই থাকে। এই প্রোগ্রামটি গ্রাফ DAG কিনা তা যাচাই করে।

এলগরিদম (সরলীকৃত)

শুরু
  Function checkDAG(n):
    count = 0, size = n - 1
    for i = 0 to n-1:
      যদি count == size: return 1 (DAG)
      যদি arr[i].ptr == NULL:
        count++
        সব নোড j-এর জন্য:
          যতক্ষণ arr[j].ptr != NULL:
            যদি arr[j].ptr->d == arr[i].ptr->d:
              arr[j].ptr->d = -1  // মার্ক করা
            arr[i].ptr = arr[i].ptr->next
    return 0 (DAG নয়)
শেষ

দ্রষ্টব্য: উপরের এলগরিদমটি একটি নিজস্ব পদ্ধতি দেখিয়েছে। স্ট্যান্ডার্ড পদ্ধতি হলো টপোলজিক্যাল সর্ট (Kahn's Algorithm) বা DFS-ভিত্তিক সাইকেল ডিটেকশন।

উদাহরণ কোড

#include <iostream>
using namespace std;

int c = 0;
struct ad_list {
    int d;
    ad_list *next;
} *np = NULL, *np1 = NULL, *p = NULL, *q = NULL;

struct Gr {
    int v;
    ad_list *ptr;
} arr[6];

void addRevEdge(int s, int d) { /* রিভার্স এজ যোগ */ }
void addEdge(int s, int d) { /* ফরওয়ার্ড এজ যোগ */ }

void print_g(int n) {
    for (int i = 0; i < n; i++) {
        cout << "Adjacency List of " << arr[i].v << ": ";
        while (arr[i].ptr != NULL) {
            cout << arr[i].ptr->d << " ";
            arr[i].ptr = arr[i].ptr->next;
        }
        cout << endl;
    }
}

int checkDAG(int n) {
    int count = 0, size = n - 1;
    for (int i = 0; i < n; i++) {
        if (count == size) return 1;
        if (arr[i].ptr == NULL) {
            count++;
            for (int j = 0; j < n; j++) {
                while (arr[j].ptr != NULL) {
                    if (arr[j].ptr->d == arr[i].ptr->d)
                        arr[j].ptr->d = -1;
                    arr[i].ptr = arr[i].ptr->next;
                }
            }
        }
    }
    return 0;
}

int main() {
    int v = 4;
    cout << "Number of vertices: " << v << endl;
    for (int i = 0; i < v; i++) {
        arr[i].v = i;
        arr[i].ptr = NULL;
    }

    addEdge(1, 0);
    addEdge(3, 1);
    addEdge(2, 1);
    addEdge(0, 3);
    addEdge(4, 1);  // নোড ৪ গ্রাফে নেই (v=4) — বাগ

    print_g(v);
    cout << "The given graph is 'Directed Acyclic Graph' :";
    if (checkDAG(v) == 1)
        cout << " yes";
    else
        cout << " no";
}

আউটপুট

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

সঠিক পদ্ধতি (Kahn's Algorithm):

bool isDAG(int V, vector<int> adj[]) {
    vector<int> indeg(V, 0);
    for (int u = 0; u < V; u++)
        for (int v : adj[u]) indeg[v]++;

    queue<int> 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;  // সব নোড প্রসেস হলে DAG
}