C++で各頂点の指定された次数からグラフを生成する方法

頂点のリストと、それぞれの頂点に割り当てられた次数（degree）が与えられたとき、その次数列から無向グラフを生成することを考えます。ここで生成するグラフには、自己ループや多重辺は含まれないものとします。

例えば、次数列が [2, 2, 1, 1] の場合、生成できるグラフは次の図のようになります。

アルゴリズムの手順

この問題は、貪欲法（グリーディ法）の考え方を使って解くことができます。具体的な手順は以下の通りです。

• グラフの構造を保存するための隣接行列 adj を定義し、すべての要素を 0 で初期化します。

• 各頂点 i について、それより後ろの頂点 j を順に調べます。

  • 頂点 i と頂点 j の次数がどちらも 0 より大きい場合、両者の次数を 1 ずつ減らし、隣接行列上で i と j を結ぶ辺を設定します（adj[i][j] = adj[j][i] = 1）。

• すべての頂点について処理が完了したら、隣接行列を整形して表示します。

サンプルコード

#include <iostream>
#include <iomanip>
using namespace std;

void generateGraph(int vert_degree[], int n) {
    int adj_mat[n][n];
    // 隣接行列を0で初期化
    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);
}

出力結果

     (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

補足：この手法の注意点

上記の貪欲なアプローチはシンプルで理解しやすい一方、与えられた次数列が「グラフィカル（実際のグラフとして構成可能）」でない場合、正しいグラフを生成できないことがあります。次数列が有効かどうかを厳密に判定したい場合は、Havel–Hakimi アルゴリズムやErdős–Gallai の定理を利用するとよいでしょう。また、計算量は頂点ペアを二重ループで走査するため O(n²) となり、頂点数が多い場合でも比較的効率的に動作します。