C++ প্রোগ্রাম: র‍্যান্ডম এজ জেনারেশন দিয়ে র‍্যান্ডম গ্রাফ তৈরি

এলগরিদম

1. ভার্টেক্স সংখ্যা `V` এবং এজ সংখ্যা `E` র‍্যান্ডমলি বা ইনপুট নিন।
2. `E` সংখ্যক এজ জেনারেট করুন: প্রতিটি এজের জন্য দুটি র‍্যান্ডম ভার্টেক্স বেছে নিন।
3. সেলফ-লুপ (u==v) এবং ডুপ্লিকেট এজ এড়ান।
4. অ্যান্ডিরেক্টেড গ্রাফ ধরে উভয় দিকের সংযোগ স্টোর করুন।
5. আইসোলেটেড ভার্টেক্স (ডিগ্রি ০) প্রিন্ট করুন।

উদাহরণ কোড

#include <iostream>
#include <vector>
#include <set>
#include <cstdlib>
#include <ctime>
using namespace std;

void generateRandomGraph(int V, int E) {
    vector<pair<int,int>> edges;
    set<pair<int,int>> edgeSet;

    while ((int)edges.size() < E) {
        int u = rand() % V;
        int v = rand() % V;
        if (u == v) continue; // No self-loop
        if (u > v) swap(u, v); // Undirected: store sorted
        if (edgeSet.count({u, v})) continue; // No duplicate
        edgeSet.insert({u, v});
        edges.push_back({u, v});
    }

    // Build adjacency list for printing
    vector<vector<int>> adj(V);
    for (auto [u, v] : edges) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    cout << "জেনারেটেড র‍্যান্ডম গ্রাফ (V=" << V << ", E=" << E << "):\n";
    for (int i = 0; i < V; i++) {
        cout << i << " -> { ";
        if (adj[i].empty()) cout << "Isolated Vertex!";
        else for (int v : adj[i]) cout << v << " ";
        cout << " }\n";
    }
}

int main() {
    srand(time(0));
    int V = 7 + rand() % 6; // 7-12 vertices
    int maxE = V * (V - 1) / 2;
    int E = rand() % (maxE + 1);

    cout << "র‍্যান্ডম গ্রাফ জেনারেশন:\n";
    cout << "ভার্টেক্স: " << V << ", এজ: " << E << "\n\n";
    generateRandomGraph(V, E);
    return 0;
}

আউটপুট উদাহরণ

র‍্যান্ডম গ্রাফ জেনারেশন:
ভার্টেক্স: 8, এজ: 18

জেনারেটেড র‍্যান্ডম গ্রাফ (V=8, E=18):
0 -> { 4 3 1 }
1 -> { 3 7 5 2 0 4 }
2 -> { 4 3 6 1 }
3 -> { 1 2 6 0 7 4 }
4 -> { 2 0 6 3 1 7 }
5 -> { 1 7 6 }
6 -> { 3 2 4 5 }
7 -> { 1 5 3 4 }

ব্যাখ্যা

প্রোগ্রামটি `rand()` ব্যবহার করে র‍্যান্ডম গ্রাফ জেনারেট করে। `set` ব্যবহার করে ডুপ্লিকেট এজ এড়ানো হয়েছে। টাইম কমপ্লেক্সিটি O(E log E) (সেট ইনসার্টের কারণে)। বড় গ্রাফের জন্য আরও দক্ষ পদ্ধতি আছে (যেমন র‍্যান্ডম পারমিউটেশন)।