C++でランダムグラフを生成するプログラム：ランダムな辺の選択による実装

本記事では、ランダムに選択された頂点と辺から構成されるランダムグラフをC++で生成するプログラムを紹介します。このプログラムの計算量は O(v×e) です。ここで v は頂点数、e は辺数を表します。

ランダムグラフとは、頂点間の接続が確率的に決定されるグラフのことで、ネットワーク解析やアルゴリズムの性能評価など、さまざまな分野で活用されています。本プログラムでは、rand() 関数を使って辺の両端となる頂点番号をランダムに決定し、自己ループ（同一頂点同士を結ぶ辺）や重複する辺を除外しながら、単純な無向グラフを構築します。

アルゴリズム

開始
　　GenRandomGraphs() 関数を作成する。引数リストには
　　辺の数「e」と頂点の数「v」を受け取る。
　　rand() 関数を使用し、グラフの頂点数と辺数にランダムな値を割り当てる。
　　方向を問わず、各頂点の接続関係を出力する。
　　次数（接続）を持たない頂点には「孤立頂点」と出力する。
終了

サンプルコード

#include<iostream>
#include<stdlib.h>
using namespace std;
void GenRandomGraphs(int NOEdge, int NOVertex) {
    int i, j, edge[NOEdge][2], count;
    i = 0;
    // rand()関数で頂点と辺にランダムな値を割り当てる
    while(i < NOEdge) {
        edge[i][0] = rand()%NOVertex+1;
        edge[i][1] = rand()%NOVertex+1;
        // 方向を問わず、各頂点の接続関係を出力する
        if(edge[i][0] == edge[i][1])
            continue;
        else {
            for(j = 0; j < i; j++) {
                if((edge[i][0] == edge[j][0] && edge[i][1] == edge[j][1]) || (edge[i][0] == edge[j][1] && edge[i][1] == edge[j][0]))i--;
            }
        }
        i++;
    }
    cout<<"\n生成されたランダムグラフ: ";
    for(i = 0; i < NOVertex; i++) {
        count = 0;
        cout<<"\n\t"<<i+1<<"-> { ";
        for(j = 0; j < NOEdge; j++) {
            if(edge[j][0] == i+1) {
                cout<<edge[j][1]<<" ";
                count++;
            } else if(edge[j][1] == i+1) {
                cout<<edge[j][0]<<" ";
                count++;
            } else if(j== NOEdge-1&& count == 0)cout<<"孤立頂点!";
            // 次数を持たない頂点には「孤立頂点」と出力する
        }
        cout<<" }";
    }
}
int main() {
    int i, e, n;
    cout<<"ランダムグラフの生成: ";
    n= 7 + rand()%6;
    cout<<"\nこのグラフは "<<n<<" 個の頂点を持ち、";
    e = rand()%((n*(n-1))/2);
    cout<<"\n"<<e<<" 本の辺を持ちます。";
    GenRandomGraphs(e, n);
}

実行結果

ランダムグラフの生成:
このグラフは 8 個の頂点を持ち、
18 本の辺を持ちます。
生成されたランダムグラフ:
    1-> { 5 4 2 }
    2-> { 4 8 6 3 1 5 }
    3-> { 5 4 7 2 }
    4-> { 2 3 7 1 8 5 }
    5-> { 3 1 7 4 2 8 }
    6-> { 2 8 7 }
    7-> { 4 3 5 6 }
    8-> { 2 6 4 5 }

処理のポイント

• 自己ループの除外： edge[i][0] == edge[i][1] の場合、その辺は採用せずに抽選をやり直します。
• 重複辺の除外： すでに登録済みの辺と同じ組み合わせ（逆向きの接続も含む）が存在する場合は、カウンタ i を減らして再抽選します。
• 孤立頂点の検出： どの辺にも接続されていない頂点には「孤立頂点!」と表示されます。

なお、n 個の頂点を持つ単純グラフの辺数の最大値は n(n-1)/2 であるため、main 関数内でもこの範囲でランダムに辺数を決定しています。実行するたびに頂点数・辺数・接続関係がすべて変化するため、テストデータの自動生成などにも応用できます。