【C++】次数列からグラフが構築可能かどうかを判定・生成するプログラムの解説

本記事では、指定された辺数と頂点数をもとに、グラフの構築が可能かどうかを確認し、ランダムな無向グラフを生成するC++プログラムを紹介します。与えられた条件(頂点数・辺数)から実際にグラフを構築できるかをチェックしながら、隣接関係を出力するまでの一連の流れを、アルゴリズムとサンプルコードを通してわかりやすく解説します。

入力

プログラムへの入力は、グラフの頂点数(vertexes)と辺数(edges)です。

出力

出力としては、生成されたグラフの各頂点に接続している頂点番号(隣接リスト形式)が表示されます。どの頂点とも接続していない孤立した頂点については、その旨が明示されます。

アルゴリズム

処理の流れは以下の通りです。

Begin
　関数 RandomGraphs() を宣言する。
　　整数型の NoEdge と NoVertex を引数として受け取る。
　　整数型の i, j, e[NoEdge][2], c を宣言する。
　　i = 0 で初期化する。
　while (i < NoEdge) の間繰り返す:
　　　e[i][0] = rand()%NoVertex+1 を設定する。
　　　e[i][1] = rand()%NoVertex+1 を設定する。
　　　もし e[i][0] == e[i][1](自己ループ)なら continue でスキップ。
　　　そうでなければ:
　　　　　j = 0 から i 未満までループし、
　　　　　すでに同じ辺(e[i][0]==e[j][0] && e[i][1]==e[j][1]、
　　　　　または e[i][0]==e[j][1] && e[i][1]==e[j][0])が存在すれば i-- して再試行。
　「The randomly generated graph:」を出力する。
　i = 0 から NoVertex-1 までループ:
　　　c = 0 で初期化。
　　　「Vertex number」と頂点番号を出力する。
　　　j = 0 から NoEdge-1 までループ:
　　　　　もし e[j][0] == i+1 なら e[j][1] の値を出力し c++。
　　　　　それ以外で e[j][1] == i+1 なら e[j][0] の値を出力し c++。
　　　　　それ以外で j == NoEdge-1 かつ c == 0 なら
　　　　　「This vertex is isolated!!!」を出力する。
End

Begin
　整数型の edg, ver を宣言する。
　「generation of a random graph:」を出力する。
　「Enter the number of vertexes for the graph:」を出力し、ver の値を入力させる。
　「Enter the number of edges for the graph:」を出力し、edg の値を入力させる。
　RandomGraphs(edg, ver) を呼び出し、
　edg 本の辺と ver 個の頂点を持つランダムな無向グラフを生成する。
End.

ポイント解説

このアルゴリズムの重要なポイントは以下の3つです。

• 自己ループの排除: 2つの乱数で選んだ頂点が同じ場合、その辺は無効として扱い、再抽選を行います。
• 重複辺の排除: 既に登録済みの辺と同じ組(順序を問わない)が現れた場合はカウントを巻き戻し(i--)、別の辺を選び直します。これにより単純グラフが保証されます。
• 隣接リストの出力: 各頂点について全ての辺を走査し、自身につながる相手側の頂点番号を出力します。1つも接続がない場合は孤立頂点として表示します。

なお、この手法は「次数列(各頂点の次数)からグラフを復元する問題(Havel–Hakimi定理など)」に関連するトピックですが、本プログラム自体は指定された頂点数・辺数からランダムに単純無向グラフを構成するアプローチを採用しています。

C++による実装例

#include<iostream>
#include<stdlib.h>
using namespace std;
void RandomGraphs(int NoEdge, int NoVertex) { // ランダムグラフの生成
    int i, j, e[NoEdge][2], c;
    i = 0;
    while(i < NoEdge) { // 2つの頂点間の接続を構築
        e[i][0] = rand()%NoVertex+1;
        e[i][1] = rand()%NoVertex+1;
        if(e[i][0] == e[i][1]) // 自己ループは除外
            continue;
        else {
            for(j = 0; j < i; j++) { // 重複辺のチェック
                if((e[i][0] == e[j][0] && e[i][1] == e[j][1]) || (e[i][0] == e[j][1] && e[i][1] == e[j][0]))
                    i--; // 重複していた場合はやり直し
            }
        }
        i++;
    }
    cout<<"The randomly generated graph: \n";
    for(i = 0; i < NoVertex; i++) { // グラフの隣接リストを出力
        c = 0;
        cout<<"Vertex number "<<i+1<<": \t { ";
        for(j = 0; j < NoEdge; j++) {
            if(e[j][0] == i+1) {
                cout<<e[j][1]<<" ";
                c++;
            } else if(e[j][1] == i+1) {
                cout<<e[j][0]<<" ";
                c++;
            } else if(j == NoEdge-1 && c == 0)
                cout<<"This vertex is isolated!!!"; // 孤立頂点の表示
        }
        cout<<" }\n";
    }
}
int main() {
    int edg, ver;
    cout<<"generation of a random graph: ";
    // 頂点数と辺数の入力を受け取る
    cout<<"\nEnter the number of vertexes for the graph: ";
    cin>>ver;
    cout<<"\nEnter the number of edges for the graph: ";
    cin>>edg;
    RandomGraphs(edg, ver); // edg 本の辺と ver 個の頂点を持つランダム無向グラフを生成
}

実行結果(出力例)

上記プログラムを実行し、頂点数5・辺数5を入力した場合の実行例は次の通りです。

generation of a random graph:
Enter the number of vertexes for the graph: 5

Enter the number of edges for the graph: 5
The randomly generated graph:
Vertex number 1: { 5 3 }
Vertex number 2: { 3 5 }
Vertex number 3: { 2 5 1 }
Vertex number 4: { This vertex is isolated!!! }
Vertex number 5: { 1 3 2 }

まとめ

本プログラムは、rand() 関数を利用して頂点のペアをランダムに選び、自己ループや重複辺を排除しながら単純無向グラフを構築します。最終的に各頂点の隣接頂点一覧(隣接リスト)を出力することで、生成されたグラフの構造を視覚的に確認できます。孤立頂点の検出も行うため、グラフ理論の学習やアルゴリズムの練習題材として非常に有用です。乱数ベースのアプローチのため、実行するたびに異なるグラフが生成される点にも注目してみてください。