ধরুন আমাদের শীর্ষবিন্দুগুলির একটি তালিকা রয়েছে এবং তাদের ডিগ্রি দেওয়া হয়েছে। আমাদের সেই ডিগ্রি ক্রম থেকে একটি অনির্দেশিত গ্রাফ তৈরি করতে হবে। এটি লুপ বা একাধিক প্রান্ত অন্তর্ভুক্ত করবে না। তাই যদি ডিগ্রী ক্রম [2, 2, 1, 1] এর মত হয়, তাহলে গ্রাফটি এরকম হতে পারে
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
গ্রাফ সঞ্চয় করার জন্য সংলগ্নতা ম্যাট্রিক্স adj সংজ্ঞায়িত করুন
-
প্রতিটি শীর্ষবিন্দুর জন্য i, do
-
প্রতিটি শীর্ষবিন্দু j এর জন্য যা বৈধ, এবং i
এর পাশে-
যদি শীর্ষবিন্দু i এবং j এর মাত্রা শূন্যের বেশি হয়, তাহলে তাদের সংযোগ করুন
-
-
-
ম্যাট্রিক্স প্রদর্শন করুন।
উদাহরণ
#include <iostream>
#include <iomanip>
using namespace std;
void generateGraph(int vert_degree[], int n) {
int adj_mat[n][n];
for(int i = 0; i<n; i++){
for(int j = 0; j < n; j++){
adj_mat[i][j] = 0;
}
}
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (vert_degree[i] > 0 && vert_degree[j] > 0) {
vert_degree[i]--; vert_degree[j]--;
adj_mat[i][j] = adj_mat[j][i] = 1;
}
}
}
cout << endl << setw(3) << " ";
for (int i = 0; i < n; i++)
cout << setw(3) << "(" << i << ")";
cout << endl << endl;
for (int i = 0; i < n; i++) {
cout << setw(4) << "(" << i << ")";
for (int j = 0; j < n; j++)
cout << setw(5) << adj_mat[i][j];
cout << endl;
}
}
int main() {
int vert_degree[] = { 2, 2, 1, 1, 1 };
int n = sizeof(vert_degree) / sizeof(vert_degree[0]);
generateGraph(vert_degree, n);
}
আউটপুট
(0) (1) (2) (3) (4) (0) 0 1 1 0 0 (1) 1 0 0 1 0 (2) 1 0 0 0 0 (3) 0 1 0 0 0 (4) 0 0 0 0 0
