Xây đồ thị từ bậc đỉnh cho trước trong C++

Cho danh sách đỉnh và bậc của chúng. Tạo đồ thị vô hướng từ dãy bậc. Không có khuyên (loop) hoặc đa cung (multiple edges). Ví dụ: [2, 2, 1, 1].

Thuật toán

1. Khởi tạo ma trận kề adj[n][n] = 0
2. Với mỗi đỉnh i:
   • Với mỗi đỉnh j > i:
   • Nếu bậc[i] > 0 và bậc[j] > 0: nối cạnh, giảm bậc cả 2
3. In ma trận kề

Chương trình C++

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

Kết quả

     (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

Lưu ý

Thuật toán tham lam này không đảm bảo luôn tìm được đồ thị nếu dãy bậc là graphic (thuộc đồ thị). Cần thuật toán Havel-Hakimi hoặc Erdős–Gallai để kiểm tra tính graphic trước.