โปรแกรม C++ สร้างกราฟสำหรับ Degree Sequence ที่กำหนด

นี่คือโปรแกรม C++ แสดงกราฟไม่มีทิศทาง (undirected graph) สำหรับ degree sequence ที่กำหนด Time complexity คือ O(v*v) และไม่รวม self-edge และ multiple edges

อัลกอริทึม

เริ่มต้น
  เพื่อสร้างกราฟ
  สร้างลูปแรกเพื่อเชื่อมต่อแต่ละ vertex 'i'
  สร้างลูปซ้อนที่สองเพื่อเชื่อมต่อ vertex 'i' ไปยัง vertex 'j' ที่ถูกต้อง ต่อจากมัน
  ถ้า degree ของ vertex 'i' และ 'j' มากกว่าศูนย์ ให้เชื่อมต่อพวกมัน
  พิมพ์ adjacency matrix โดยใช้ PrintMatrix()
สิ้นสุด

โค้ดตัวอย่าง

#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 << "Enter the number of vertex in the graph: ";
    cin >> N;
    int degseq[N];
    for(i = 0; i < N; i++) {
        cout << "Enter the degree of " << i+1 << " vertex: ";
        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);
}

ผลลัพธ์ตัวอย่าง

Enter the number of vertex in the graph: 5
Enter the degree of 1 vertex: 4
Enter the degree of 2 vertex: 2
Enter the degree of 3 vertex: 1
Enter the degree of 4 vertex: 2
Enter the degree of 5 vertex: 1

(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