परिचय
यह एक C++ प्रोग्राम है जो दिए गए डिग्री सीक्वेंस के लिए एक अनडायरेक्टेड ग्राफ को दर्शाता है। इस एल्गोरिदम की समय जटिलता O(v*v) है और इसमें सेल्फ-एज और मल्टीपल एज शामिल नहीं हैं।
एल्गोरिदम
ग्राफ बनाने के लिए, प्रत्येक वर्टेक्स '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);
return 0;
}
आउटपुट
ग्राफ में वर्टेक्स की संख्या दर्ज करें: 5 वर्टेक्स 1 की डिग्री दर्ज करें: 4 वर्टेक्स 2 की डिग्री दर्ज करें: 2 वर्टेक्स 3 की डिग्री दर्ज करें: 1 वर्टेक्स 4 की डिग्री दर्ज करें: 2 वर्टेक्स 5 की डिग्री दर्ज करें: 1 (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
