Xây dựng một đồ thị từ các bậc đã cho của tất cả các đỉnh trong C ++

Giả sử chúng ta có một danh sách các đỉnh, và độ của chúng đã cho. Chúng ta phải tạo một đồ thị vô hướng từ chuỗi mức độ đó. Nó sẽ không bao gồm vòng lặp hoặc nhiều cạnh. Vì vậy, nếu chuỗi độ giống như [2, 2, 1, 1], thì biểu đồ có thể giống như

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định điều từ ma trận kề để lưu trữ biểu đồ

• đối với mỗi đỉnh i, thực hiện

  • cho mỗi đỉnh j hợp lệ và bên cạnh i

    • nếu bậc của đỉnh i và j lớn hơn 0, thì nối chúng

• hiển thị ma trận.

Ví dụ

#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);
}

Đầu ra

      (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