সি++ প্রোগ্রাম: র‍্যান্ডম এজ সিলেকশন মেথড দিয়ে র‍্যান্ডম গ্রাফ কনস্ট্রাক্ট করা

এই প্রোগ্রামে র‍্যান্ডম ভের্টেক্স এবং এজের জন্য একটি র‍্যান্ডম গ্রাফ জেনারেট করা হয়। এই প্রোগ্রামের টাইম কমপ্লেক্সিটি O(v*e)। যেখানে v হলো ভের্টেক্সের সংখ্যা এবং e হলো এজের সংখ্যা।

আলগরিদম

Begin
    Develop a function GenRandomGraphs(), with 'e' as the number of edges and 'v' as the number of vertexes, in the argument list.
    Assign random values to the number of vertex and edges of the graph, Using rand() function.
    Print the connections of each vertex, irrespective of the direction.
    Print "Isolated vertex" for the vertex having no degree.
End

উদাহরণ

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

void GenRandomGraphs(int NOEdge, int NOVertex) {
    int i, j, edge[NOEdge][2], count;
    i = 0;
    while (i < NOEdge) {
        edge[i][0] = rand() % NOVertex + 1;
        edge[i][1] = rand() % NOVertex + 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 < NOVertex; i++) {
        count = 0;
        cout << "\n\t" << i+1 << "-> { ";
        for (j = 0; j < NOEdge; 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 == NOEdge-1 && count == 0)
                cout << "Isolated Vertex!";
        }
        cout << " }";
    }
}

int main() {
    int i, 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);
}

আউটপুট

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 }