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