Đây là chương trình C++ biểu diễn đồ thị vô hướng cho chuỗi bậc (degree sequence) cho trước. Độ phức tạp thời gian là O(v*v) và không bao gồm khuyên (self-edge) và đa cung (multiple edges).
Thuật toán
Bắt đầu
Để tạo đồ thị,
Tạo vòng lặp đầu tiên để kết nối mỗi đỉnh 'i'.
Tạo vòng lặp lồng thứ hai để kết nối đỉnh 'i' với mọi đỉnh 'j' hợp lệ, kế tiếp nó.
Nếu bậc của đỉnh 'i' và 'j' đều lớn hơn 0, thì kết nối chúng.
In ma trận kề bằng PrintMatrix().
Kết thúc
Mã ví dụ
#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 << "Nhập số đỉnh trong đồ thị: ";
cin >> N;
int degseq[N];
for(i = 0; i < N; i++) {
cout << "Nhập bậc của đỉnh " << 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);
}
Kết quả đầu ra
Nhập số đỉnh trong đồ thị: 5 Nhập bậc của đỉnh 1: 4 Nhập bậc của đỉnh 2: 1 Nhập bậc của đỉnh 3: 1 Nhập bậc của đỉnh 4: 2 Nhập bậc của đỉnh 5: 2 (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