C++ प्रोग्राम रैंडम एज सिलेक्शन मेथड द्वारा रैंडम ग्राफ बनाने के लिए

इस प्रोग्राम में रैंडम वर्टेक्सेस और एजेस के लिए एक रैंडम ग्राफ जनरेट किया जाता है। इस प्रोग्राम की समय जटिलता O(V*E) है। जहाँ V वर्टेक्सेस की संख्या है और E एजेस की संख्या है।

एल्गोरिदम

1. GenRandomGraphs() फंक्शन विकसित करें, जिसमें 'e' एजेस की संख्या और 'v' वर्टेक्सेस की संख्या हो।
2. rand() फंक्शन का उपयोग करके ग्राफ के वर्टेक्स और एजेस की संख्या को रैंडम मान असाइन करें।
3. प्रत्येक वर्टेक्स के कनेक्शन्स प्रिंट करें, दिशा की परवाह किए बिना।
4. जिन वर्टेक्सेस की डिग्री शून्य है, उनके लिए "Isolated vertex" प्रिंट करें।

C++ कार्यान्वयन

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

void GenRandomGraphs(int numEdges, int numVertices) {
    int i, j, edge[100][2], count;
    i = 0;
    while (i < numEdges) {
        edge[i][0] = rand() % numVertices + 1;
        edge[i][1] = rand() % numVertices + 1;
        if (edge[i][0] == edge[i][1]) continue;
        else {
            for (j = 0; j < i; j++) {
                if ((edge[i][0] == edge[j][0] && edge[i][1] == edge[j][1]) ||
                    (edge[i][0] == edge[j][1] && edge[i][1] == edge[j][0]))
                    i--;
            }
        }
        i++;
    }
    cout << "\nThe generated random graph is: ";
    for (i = 0; i < numVertices; i++) {
        count = 0;
        cout << "\n\t" << i+1 << "-> { ";
        for (j = 0; j < numEdges; j++) {
            if (edge[j][0] == i+1) {
                cout << edge[j][1] << " ";
                count++;
            } else if (edge[j][1] == i+1) {
                cout << edge[j][0] << " ";
                count++;
            } else if (j == numEdges-1 && count == 0)
                cout << "Isolated Vertex!";
        }
        cout << " }";
    }
}

int main() {
    int e, n;
    cout << "Random graph generation: ";
    n = 7 + rand() % 6;
    cout << "\nThe graph has " << n << " vertices";
    e = rand() % ((n * (n-1)) / 2);
    cout << "\nand has " << e << " edges.";
    GenRandomGraphs(e, n);
    return 0;
}

आउटपुट

Random graph generation: 
The graph has 8 vertices
and has 18 edges.
The generated random graph is:
    1-> { 5 4 2 }
    2-> { 4 8 6 3 1 5 }
    3-> { 5 4 7 2 }
    4-> { 2 3 7 1 8 5 }
    5-> { 3 1 7 4 2 8 }
    6-> { 2 8 7 }
    7-> { 4 3 5 6 }
    8-> { 2 6 4 5 }