এই প্রোগ্রামে আমরা দত্তক এজ 'e' অনুযায়ী র্যান্ডম ডাইরেক্টেড অ্যাসাইক্লিক গ্রাফ (DAG) জেনারেট করব। এই প্রোগ্রামের টাইম কমপ্লেক্সিটি O(e*v*e)।
অ্যালগরিদম
শুরু
GenerateRandomGraphs() ফাংশন, যেটি 'e' নাম্বার অফ এজ আর্গুমেন্ট হিসেবে নেয়
দুটি র্যান্ডম নম্বরের মধ্যে কানেকশন জেনারেট করুন, স্যাম্পল কেসের জন্য ভের্টেক্স লিমিট ২০ রাখুন
CheckAcyclic() ব্যবহার করে গ্রাফে সাইকেল আছে কিনা চেক করুন
যদি false রিটার্ন করে তবে এই এজ বাতিল করুন
অন্যথায় গ্রাফে এজটি রাখুন
প্রতিটি ভের্টেক্সের ডাইরেক্টেড কানেকশন প্রিন্ট করুন
যদি কোনো ভের্টেক্সের ইন+আউট ডিগ্রি শূন্য হয় তবে সেটিকে "isolated vertex" হিসেবে প্রিন্ট করুন
শেষ
উদাহরণ কোড
#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]);
}
}
}
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 << "\nThe generated random random graph is: ";
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);
}
আউটপুট
র্যান্ডম গ্রাফের জন্য এজ সংখ্যা দিন: 4
The generated random random graph is:
1-> { }
2-> { 8 }
3-> { 5 }
4-> { Isolated Vertex! }
5-> { 1 }
6-> { Isolated Vertex! }
7-> { Isolated Vertex! }
8-> { }
9-> { Isolated Vertex! }
10-> { 5 }
