指定した次数列からグラフを生成するC++プログラムの実装方法

本記事では、与えられた次数列（degree sequence）をもとに無向グラフを構築するC++プログラムを紹介します。このアルゴリズムの時間計算量は O(v²) であり、自己ループや多重辺は含まれません。生成したグラフの構造は、隣接行列として出力されます。

アルゴリズムの手順

1. 各頂点「i」を走査する外側のループを作成します。
2. 頂点「i」より後ろにある各頂点「j」を調べる内側のループ（ネストされたループ）を作成します。
3. 頂点「i」と頂点「j」の残り次数がどちらも0より大きい場合、両者を結ぶ辺を追加し、それぞれの次数を1ずつ減らします。
4. 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;
    int AdjMat[20][20] = {0};

    cout << "グラフの頂点数を入力してください: ";
    cin >> N;

    int degseq[N];
    for (i = 0; i < N; i++) {
        cout << "頂点" << 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);
    return 0;
}

実行結果

たとえば、頂点数4・次数列「2, 2, 1, 1」を入力した場合の実行例は以下のとおりです。

グラフの頂点数を入力してください: 4
頂点1の次数を入力してください: 2
頂点2の次数を入力してください: 2
頂点3の次数を入力してください: 1
頂点4の次数を入力してください: 1

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

 (1)    0    1    1    0

 (2)    1    0    0    1

 (3)    1    0    0    0

 (4)    0    1    0    0

解説と注意点

この実行例では、次数列「2, 2, 1, 1」から頂点1–2、1–3、2–4を結ぶパスグラフ（木構造）が生成されています。隣接行列は対称行列となり、対角成分はすべて0です。これは自己ループが存在しないことを意味します。

ただし、このプログラムは残り次数を持つ頂点同士を単純に貪欲法（greedy）で接続していく方式のため、入力された次数列がグラフとして実現可能（可グラフ）であっても、必ずしもその次数列どおりのグラフが得られるとは限りません。厳密に判定・構成したい場合は、Havel–HakimiアルゴリズムやErdős–Gallaiの定理を併用することをおすすめします。

計算量は頂点数をvとすると O(v²) です。また、隣接行列は最大20×20の固定サイズ配列として定義しているため、それ以上の頂点数を扱う場合は配列サイズの変更や、std::vector を使った動的な確保を検討してください。