এটি একটি অনির্দেশিত গ্রাফ (undirected graph) রিপ্রেজেন্ট করে দত্তক ডিগ্রি সিকোয়েন্স (degree sequence) অনুযায়ী। এই অ্যালগরিদমের টাইম কমপ্লেক্সিটি O(v*v) এবং এতে সেলফ-এজ (self-edge) এবং মাল্টিপল এজ (multiple edges) থাকে না।
অ্যালগরিদম
শুরু
গ্রাফ তৈরি করতে
প্রতিটি ভের্টেক্স 'i' কানেক্ট করার জন্য প্রথম লুপ তৈরি করুন
ভের্টেক্স 'i' কে এর পাশের সব ভ্যালিড ভের্টেক্স 'j'-এর সাথে কানেক্ট করার জন্য দ্বিতীয় নেস্টেড লুপ তৈরি করুন
যদি ভের্টেক্স 'i' এবং 'j'-এর ডিগ্রি শূন্যের চেয়ে বড় হয়, তবে সেগুলো কানেক্ট করুন
PrintMatrix() ব্যবহার করে অ্যাডজেসেন্সি ম্যাট্রিক্স প্রিন্ট করুন
শেষ
উদাহরণ কোড
#include <iostream>
#include <iomanip>
using namespace std;
void PrintMatrix(int matrix[][20], int n) {
int i, j;
cout << "\n\n" << setw(3) << " ";
for(i = 0; i < n; i++)
cout << setw(3) << "(" << i+1 << ")";
cout << "\n\n";
for(i = 0; i < n; i++) {
cout << setw(4) << "(" << i+1 << ")";
for(j = 0; j < n; j++) {
cout << setw(5) << matrix[i][j];
}
cout << "\n\n";
}
}
int main() {
int N, i, j, AdjMat[20][20] = {0};
cout << "গ্রাফের ভের্টেক্স সংখ্যা দিন: ";
cin >> N;
int degseq[N];
for(i = 0; i < N; i++) {
cout << i+1 << " নম্বর ভের্টেক্সের ডিগ্রি দিন: ";
cin >> degseq[i];
}
for(i = 0; i < N; i++) {
for(j = i+1; j < N; j++) {
if(degseq[i] > 0 && degseq[j] > 0) {
degseq[i]--;
degseq[j]--;
AdjMat[i][j] = 1;
AdjMat[j][i] = 1;
}
}
}
PrintMatrix(AdjMat, N);
}
আউটপুট
গ্রাফের ভের্টেক্স সংখ্যা দিন: 5 ১ নম্বর ভের্টেক্সের ডিগ্রি দিন: 4 ২ নম্বর ভের্টেক্সের ডিগ্রি দিন: 2 ৩ নম্বর ভের্টেক্সের ডিগ্রি দিন: 1 ৪ নম্বর ভের্টেক্সের ডিগ্রি দিন: 2 ৫ নম্বর ভের্টেক্সের ডিগ্রি দিন: 2 (1) (2) (3) (4) (5) (1) 0 1 1 1 1 (2) 1 0 0 1 0 (3) 1 0 0 0 0 (4) 1 1 0 0 1 (5) 1 0 0 1 0
