C++ प्रोग्राम: दिए गए एज की संख्या के लिए रैंडम डायरेक्टेड एसाइक्लिक ग्राफ (DAG) जनरेट करें

परिचय

इस प्रोग्राम में हम दिए गए एज 'e' के लिए एक रैंडम डायरेक्टेड एसाइक्लिक ग्राफ जनरेट करते हैं। इस प्रोग्राम की समय जटिलता O(e*v*e) है।

एल्गोरिदम

GenerateRandomGraphs() फ़ंक्शन में 'e' को एज की संख्या के रूप में लें। दो रैंडम नंबर के बीच एक कनेक्शन जनरेट करें, एक छोटे केस के लिए वर्टेक्स की संख्या को 20 तक सीमित करें। CheckAcyclic() का उपयोग करके ग्राफ में साइकिल की जांच करें, यदि यह false लौटाता है तो इस एज को त्याग दें, अन्यथा ग्राफ में एज को बनाए रखें। प्रत्येक वर्टेक्स के सभी डायरेक्टेड कनेक्शन प्रिंट करें। यदि किसी वर्टेक्स की इन+आउट डिग्री शून्य है तो उसे "आइसोलेटेड वर्टेक्स" के रूप में प्रिंट करें।

उदाहरण कोड

#include <iostream>
#include <stdlib.h>
#define N 10
using namespace std;

bool Checkcyclic(int ed[][2], int edge, bool check[], int v) {
    int i;
    // यदि वर्तमान वर्टेक्स पहले से विजिट किया गया है, तो ग्राफ में साइकिल है।
    if (check[v] == true) {
        return false;
    } else {
        check[v] = true;
        // प्रत्येक वर्टेक्स के लिए, उससे जुड़े सभी वर्टेक्स पर जाएं।
        for (i = edge; i >= 0; i--) {
            if (ed[i][0] == v) {
                return Checkcyclic(ed, edge, check, ed[i][1]);
            }
        }
    }
    // यदि पथ समाप्त होता है तो उस पथ में विजिट किए गए वर्टेक्स को फिर से false असाइन करें।
    check[v] = false;
    if (i == 0)
        return true;
}

void GenerateRandomGraphs(int e) {
    int i, j, ed[e][2], count;
    bool c[11];
    i = 0;
    while (i < e) {
        ed[i][0] = rand() % N + 1;
        ed[i][1] = rand() % N + 1;
        for (j = 1; j <= 10; j++)
            c[j] = false;
        if (Checkcyclic(ed, i, c, ed[i][0]) == true)
            i++;
    }
    cout << "\nजनरेट किया गया रैंडम ग्राफ है: ";
    for (i = 0; i < N; i++) {
        count = 0;
        cout << "\n\t" << i+1 << "-> { ";
        for (j = 0; j < e; j++) {
            if (ed[j][0] == i+1) {
                cout << ed[j][1] << " ";
                count++;
            } else if (ed[j][1] == i+1) {
                count++;
            } else if (j == e-1 && count == 0)
                cout << "Isolated Vertex!";
        }
        cout << " }";
    }
}

int main() {
    int e;
    cout << "रैंडम ग्राफ के लिए एज की संख्या दर्ज करें: ";
    cin >> e;
    GenerateRandomGraphs(e);
    return 0;
}

आउटपुट

रैंडम ग्राफ के लिए एज की संख्या दर्ज करें: 4
जनरेट किया गया रैंडम ग्राफ है:
1-> { }
2-> { 8 }
3-> { 5 }
4-> { Isolated Vertex! }
5-> { 1 }
6-> { Isolated Vertex! }
7-> { Isolated Vertex! }
8-> { }
9-> { Isolated Vertex! }
10-> { 5 }