指定したエッジ数からランダムな無向グラフを生成するC++プログラムの解説

本記事では、指定されたエッジ数「e」をもとに、ランダムな無向グラフを生成するC++プログラムを解説します。乱数を利用して頂点間の接続を自動的に作成するこの手法は、大規模ネットワークのモデリングやグラフ理論の学習、アルゴリズムのテストデータ作成などに幅広く活用できます。

アルゴリズムの流れ

GenerateRandomGraphs()関数は、引数としてエッジ数「e」を受け取ります。まずrand()関数で2つの頂点番号をランダムに選んでエッジを生成し、その後すべての頂点について接続先を走査して出力します。処理の流れは以下のとおりです。

開始
    関数 GenerateRandomGraphs() は、引数としてエッジ数 'e' を受け取る
    i = 0 で初期化
    while(i < e)
        edge[i][0] = rand()%N+1
        edge[i][1] = rand()%N+1
        i をインクリメント
    i = 0 から N-1 まで繰り返す
        count = 0 で初期化
        j = 0 から e-1 まで繰り返す
            if(edge[j][0] == i+1)
                edge[j][1] を出力し、count を増加
            else if(edge[j][1] == i+1)
                edge[j][0] を出力し、count を増加
            else if(j == e-1 かつ count == 0)
                「孤立頂点」を出力
終了

サンプルコード

以下は、頂点数を10に固定し、ユーザーが入力したエッジ数に応じてランダムグラフを生成・表示する完全なC++コードです。

#include<iostream>
#include<stdlib.h>
#define N 10
using namespace std;
void GenerateRandomGraphs(int e) {
    int i, j, edge[e][2], count;
    i = 0;
    // 2つの乱数の間に接続を生成する(サンプル用に頂点数は10に制限)
    while(i < e) {
        edge[i][0] = rand()%N+1;
        edge[i][1] = rand()%N+1;
        i++;
    }
    // 各頂点の接続を、向きに関係なくすべて出力する
    cout<<"\nThe generated random graph is: ";
    for(i = 0; i < N; i++) {
        count = 0;
        cout<<"\n\t"<<i+1<<"-> { ";
        for(j = 0; j < e; j++) {
            if(edge[j][0] == i+1) {
                cout<<edge[j][1]<<" ";
                count++;
            }
            else if(edge[j][1] == i+1) {
                cout<<edge[j][0]<<" ";
                count++;
            }
            // 次数0の頂点には「孤立頂点」と表示する
            else if(j == e-1 && count == 0)
                cout<<"Isolated Vertex!";
        }
        cout<<" }";
    }
}
int main() {
    int n, i ,e;
    cout<<"Enter the number of edges for the random graphs: ";
    cin>>e;
    GenerateRandomGraphs(e);
}

実行結果

エッジ数として「10」を入力した場合の実行例です。

Enter the number of edges for the random graphs: 10

The generated random graph is:
1-> { 10 7 }
2-> { 10 }
3-> { 7 8 7 }
4-> { 7 6 7 }
5-> { Isolated Vertex! }
6-> { 8 4 }
7-> { 4 3 4 1 3 }
8-> { 6 3 }
9-> { Isolated Vertex! }
10-> { 2 1 }

コードのポイント

• エッジの生成: rand()%N+1 により、1〜Nの範囲から頂点番号を2つ選び、それらを結ぶエッジとして記録します。同一エッジや自己ループが発生することもありますが、ランダムグラフとしては許容されます。
• 隣接頂点の表示: 各頂点について全エッジを走査し、始点または終点が一致するものを探して接続先を出力します。無向グラフのため向きは区別しません。
• 孤立頂点の判定: どのエッジにも現れなかった頂点(次数0)は「Isolated Vertex!」と表示されます。
• 計算量: エッジの生成はO(e)、隣接関係の表示はO(N×e)の計算量となります。

なお、実行するたびに異なるグラフを得たい場合は、main関数の冒頭でsrand(time(NULL))を呼び出して乱数のシードを初期化します(その際は<ctime>のインクルードが必要です)。頂点数Nは#defineディレクティブで定義されているため、必要に応じて変更できます。