मान लीजिए हमारे पास शीर्षों की एक सूची है, और उनकी डिग्री दी गई है। हमें उस डिग्री अनुक्रम से एक अनिर्देशित ग्राफ उत्पन्न करना है। इसमें लूप या एकाधिक एज शामिल नहीं होंगे। तो यदि डिग्री अनुक्रम [2, 2, 1, 1] जैसा है, तो ग्राफ इस तरह हो सकता है
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
ग्राफ स्टोर करने के लिए आसन्न मैट्रिक्स adj परिभाषित करें
प्रत्येक शीर्ष i के लिए, करें
प्रत्येक शीर्ष 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
