C++ प्रोग्राम: जांचें कि क्या दिए गए डिग्री सीक्वेंस के लिए ग्राफ बनाना संभव है

यह एक प्रोग्राम है जो दिए गए डिग्री सीक्वेंस में ग्राफ के निर्माण की संभावना की जांच करता है।

इनपुट

यह एजेस और वर्टेक्स की संख्या लेता है।

आउटपुट

यह बने ग्राफ के रैंडम मान दिखाता है।

एल्गोरिदम

Begin
    RandomGraphs() फंक्शन घोषित करें।
        NoEdge और NoVertex को इंटीजर डेटाटाइप का घोषित करें और उन्हें पैरामीटर के रूप में पास करें।
        i, j, e[NoEdge][2], c को इंटीजर डेटाटाइप का घोषित करें।
        i = 0 इनिशियलाइज़ करें।
        while (i < NoEdge) करें
            e[i][0] = rand()%NoVertex+1.
            e[i][1] = rand()%NoVertex+1.
            if(e[i][0] == e[i][1]) तो
                continue.
            अन्यथा
                for(j = 0; j < i; j++)
                    if((e[i][0] == e[j][0] && e[i][1] == e[j][1]) || (e[i][0] == e[j][1] && e[i][1] == e[j][0])) तो
                        i--.
                i++.
            "The randomly generated graph:" प्रिंट करें।
        for(i = 0 से NoVertex-1 तक)
            c = 0;
            "Vertex number" प्रिंट करें।
            वर्टेक्स नंबर प्रिंट करें।
            for(j = 0 से NoEdge-1 तक)
                if(e[j][0] == i+1) तो
                    e[j][1] का मान प्रिंट करें।
                    c++.
                अन्यथा if(e[j][1] == i+1) तो
                    e[j][0] का मान प्रिंट करें।
                    c++.
                अन्यथा if(j == NoEdge-1 और c == 0) तो
                    "This vertex is isolated!!!" प्रिंट करें।
End

Begin
    edg, ver को इंटीजर डेटाटाइप का घोषित करें।
    "generation of a random graph:" प्रिंट करें।
    "Enter the number of vertexes for the graph:" प्रिंट करें।
    ver वेरिएबल का मान इनपुट लें।
    "Enter the number of edges for the graph:" प्रिंट करें।
    edg वेरिएबल का मान इनपुट लें।
    RandomGraphs(edg, ver) कॉल करें edg एजेस और ver वर्टेक्स के साथ रैंडम अनडायरेक्टेड ग्राफ जनरेट करने के लिए।
End.

उदाहरण

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

void RandomGraphs(int NoEdge, int NoVertex) { // रैंडम ग्राफ जनरेट करें
    int i, j, e[NoEdge][2], c;
    i = 0;
    
    while(i < NoEdge) { // दो वर्टेक्स के बीच कनेक्शन बनाएं
        e[i][0] = rand() % NoVertex + 1;
        e[i][1] = rand() % NoVertex + 1;
        
        if(e[i][0] == e[i][1])
            continue;
        else {
            for(j = 0; j < i; j++) {
                if((e[i][0] == e[j][0] && e[i][1] == e[j][1]) || (e[i][0] == e[j][1] && e[i][1] == e[j][0]))
                    i--;
            }
        }
        i++;
    }
    
    cout << "The randomly generated graph: \n";
    for(i = 0; i < NoVertex; i++) {
        c = 0;
        cout << "Vertex number " << i+1 << ": \t { ";
        for(j = 0; j < NoEdge; j++) {
            if(e[j][0] == i+1) {
                cout << e[j][1] << " ";
                c++;
            } else if(e[j][1] == i+1) {
                cout << e[j][0] << " ";
                c++;
            } else if(j == NoEdge-1 && c == 0)
                cout << "This vertex is isolated!!!";
        }
        cout << " }\n";
    }
}

int main() {
    int edg, ver;
    cout << "generation of a random graph: ";
    // वर्टेक्स और एजेस का इनपुट लें
    cout << "\nEnter the number of vertexes for the graph: ";
    cin >> ver;
    cout << "\nEnter the number of edges for the graph: ";
    cin >> edg;
    
    RandomGraphs(edg, ver); // edg एजेस और ver वर्टेक्स के साथ रैंडम अनडायरेक्टेड ग्राफ जनरेट करने के लिए फंक्शन कॉल करें
    return 0;
}

आउटपुट

generation of a random graph:
Enter the number of vertexes for the graph: 5
Enter the number of edges for the graph: 5
The randomly generated graph:
Vertex number 1: { 5 3 }
Vertex number 2: { 3 5 }
Vertex number 3: { 2 5 1 }
Vertex number 4: { This vertex is isolated!!! }
Vertex number 5: { 1 3 2 }

नोट: यह प्रोग्राम वास्तव में डिग्री सीक्वेंस की ग्राफिकल होने की जांच (हवेल-हाकिमी एल्गोरिदम या एर्डोस-गैलाई प्रमेय का उपयोग करके) नहीं करता है। इसके बजाय, यह दिए गए वर्टेक्स और एज काउंट के साथ एक रैंडम ग्राफ जनरेट करता है। एक वैध डिग्री सीक्वेंस चेकर दिए गए डिग्री सीक्वेंस को इनपुट के रूप में लेगा और यह सत्यापित करेगा कि क्या कोई सिंपल ग्राफ उन डिग्री को प्राप्त कर सकता है।