【C++】ランダムな辺の生成でランダムグラフを作成するプログラム

このプログラムでは、ランダムに決定した頂点数と辺数をもとに、無向のランダムグラフを生成します。時間計算量は O(v × e) です。ここで v は頂点の数、e は辺の数を表します。

アルゴリズム

開始
　　関数 GenRandomGraphs() を用意する。引数として辺の数「e」と頂点の数「v」を受け取る。
　　　　rand() 関数を使って、グラフの頂点と辺にランダムな値を割り当てる。
　　　　各頂点の接続先を、方向を区別せずに出力する。
　　　　次数（つながり）を持たない頂点には「孤立頂点」と表示する。
終了

C++による実装例

#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<<"\nThe generated random graph is: ";
    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<<"Isolated Vertex!"; // 次数0の頂点は孤立頂点として表示
        }
        cout<<" }";
    }
}

int main()
{
    int i, e, n;
    cout<<"Random graph generation: ";
    n = 7 + rand()%6;          // 頂点数を7〜12の範囲でランダムに決定
    cout<<"\nThe graph has "<<n<<" vertices";
    e = rand()%((n*(n-1))/2);  // 辺数は最大 n*(n-1)/2 未満のランダム値
    cout<<"\nand has "<<e<<" edges.";
    GenRandomGraphs(e, n);
}

コードのポイント

• 自己ループの除外：辺の両端が同じ頂点（edge[i][0] == edge[i][1]）になる場合は、その辺を生成し直します。
• 重複辺の除外：すでに登録されている辺と同じ組み合わせ（頂点の順序が逆の場合も含む）は、カウンタを巻き戻して再度生成します。
• 孤立頂点の判定：どの辺にも接続していない次数0の頂点には「Isolated Vertex!」と表示されます。

なお、実行するたびに異なるグラフを生成したい場合は、main() の冒頭で srand(time(NULL)); を呼び出して乱数系列を初期化しておくとよいでしょう（その際は #include<time.h> の追加が必要です）。

実行結果

Random graph generation:
The graph has 8 vertices
and has 18 edges.
The generated random graph is:
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 }

計算量について

このプログラムの時間計算量は O(v × e) です。新しい辺を生成するたびに既存の辺との重複チェックを行い、さらに全頂点についてすべての辺を走査して接続関係を出力するためです。頂点数や辺数が大きくなると処理時間が増加するため、大規模なグラフを扱う場合は隣接リストなどのデータ構造を活用する工夫が有効です。