고정 차수 수열로 그래프를 생성하는 C++ 프로그램

개요

이 C++ 프로그램은 사용자가 입력한 차수 수열(degree sequence)에 대응하는 무방향 그래프(undirected graph)를 생성하고, 그 결과를 인접 행렬(adjacency matrix) 형태로 출력합니다. 알고리즘의 시간 복잡도는 O(v²)이며, 자기 루프(self-loop)와 중복 간선(multiple edge)은 포함하지 않습니다.

차수 수열이란 그래프를 구성하는 각 정점에 연결된 간선의 개수를 순서대로 나열한 값입니다. 이 프로그램은 모든 정점 쌍을 검사하면서 두 정점의 남은 차수가 모두 0보다 클 때 간선을 하나씩 배치하는 탐욕(greedy) 방식으로 그래프를 완성해 나갑니다.

알고리즘

Begin
    그래프를 생성하기 위해,
    각 정점 'i'를 처리하는 첫 번째 루프를 만듭니다.
    정점 'i'를 그 뒤에 있는 유효한 모든 정점 'j'와 비교하는 두 번째 중첩 루프를 만듭니다.
    정점 'i'와 'j'의 차수가 모두 0보다 크면 두 정점을 연결합니다.
    PrintMatrix() 함수를 호출해 인접 행렬을 출력합니다.
End

예제 코드

#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: 3
Enter the degree of 2 vertex: 2
Enter the degree of 3 vertex: 1
Enter the degree of 4 vertex: 1
Enter the degree of 5 vertex: 1

       (1)  (2)  (3)  (4)  (5)

  (1)    0    1    1    1    0

  (2)    1    0    0    0    1

  (3)    1    0    0    0    0

  (4)    1    0    0    0    0

  (5)    0    1    0    0    0

코드 설명

• PrintMatrix(): 인접 행렬을 보기 좋게 정렬해 출력하는 함수입니다. setw() 조작자로 열 너비를 맞춰 행과 열의 레이블을 함께 표시합니다.
• 간선 배치 로직: 바깥 루프의 i는 현재 정점, 안쪽 루프의 j는 i보다 뒤에 있는 정점을 가리킵니다. 두 정점의 남은 차수가 모두 0보다 크면 간선을 추가하고 양쪽 차수를 1씩 감소시킵니다. j를 i+1부터 시작하기 때문에 자기 루프와 중복 간선이 자연스럽게 방지됩니다.
• AdjMat 배열: 무방향 그래프이므로 인접 행렬이 대칭이 되도록 AdjMat[i][j]와 AdjMat[j][i]를 함께 1로 설정합니다.

참고 사항

이 탐욕적 접근 방식은 모든 입력에 대해 유효한 그래프를 보장하지 않습니다. 주어진 차수 수열이 실제 그래프로 실현 가능한지는 에르되시–갈라이(Erdős–Gallai) 정리나 하벨–하키미(Havel–Hakimi) 알고리즘으로 먼저 검증하는 것이 안전합니다. 또한 예제 코드의 int degseq[N]처럼 배열 크기를 변수로 지정하는 가변 길이 배열(VLA)은 표준 C++이 아니므로, 이식성을 높이려면 std::vector<int>를 사용하는 것이 좋습니다.