指定した辺の数からランダムな有向非巡回グラフ（DAG）を生成するC++プログラム

この記事では、指定した辺の数 e に基づいて、ランダムな有向非巡回グラフ（DAG：Directed Acyclic Graph） を生成するC++プログラムを紹介します。有向非巡回グラフとは、方向性のある辺（矢印）で頂点同士を結びながらも、どこを起点にしても元の頂点へ戻ってくる閉路（サイクル）が一切存在しないグラフのことです。本プログラムの時間計算量は O(e×v×e) です。

アルゴリズム

開始
　　関数 GenerateRandomGraphs() は、引数として辺の数 e を受け取る。
　　2つの乱数の間に接続（辺）を生成する。動作確認用の小さなケースでは、頂点数を20に制限する。
　　CheckAcyclic() 関数を使用して、グラフにサイクルが発生していないかをチェックする。
　　false が返された場合は、その辺を破棄する。
　　　それ以外の場合は、その辺をグラフに保持する。
　　各頂点のすべての有向接続（隣接頂点）を出力する。
　　ある頂点の入次数と出次数の合計が0である場合、その頂点を「孤立頂点」として出力する。
終了

サンプルコード

#include<iostream>
#include<stdlib.h>
#define N 10
using namespace std;

// 新しい辺を追加した際にサイクルが発生しないかをチェックする関数
bool Checkcyclic(int ed[][2], int edge, bool check[], int v) {
    int i;
    // 現在の頂点をすでに訪問済みの場合、グラフにはサイクルが存在する
    if(check[v] == true) {
        return false;
    } else {
        check[v] = true;
        // 各頂点について、その頂点に接続されたすべての頂点を辿る
        for(i = edge; i >= 0; i--) {
            if(ed[i][0] == v) {
                return Checkcyclic(ed, edge, check, ed[i][1]);
            }
        }
    }
    // パスが終端に達したら、そのパス上で訪問済みとした頂点を再び false に戻す
    check[v] = false;
    if(i == 0)
        return true;
}

void GenerateRandomGraphs(int e) {
    int i, j, ed[e][2], count;
    bool c[11];
    i = 0;
    while(i < e) {
        ed[i][0] = rand()%N+1;
        ed[i][1] = rand()%N+1;
        for(j = 1; j <= 10; j++)
            c[j] = false;
        if(Checkcyclic(ed, i, c, ed[i][0]) == true)
            i++;
    }
    cout<<"\n生成されたランダムグラフは次の通りです: ";
    for(i = 0; i < N; i++) {
        count = 0;
        cout<<"\n\t"<<i+1<<"-> { ";
        for(j = 0; j < e; j++) {
            if(ed[j][0] == i+1) {
                cout<<ed[j][1]<<" ";
                count++;
            } else if(ed[j][1] == i+1) {
                count++;
            } else if(j == e-1 && count == 0)
                cout<<"孤立頂点！";
        }
        cout<<" }";
    }
}

int main() {
    int e;
    cout<<"ランダムグラフの辺の数を入力してください: ";
    cin>>e;
    GenerateRandomGraphs(e);
}

実行結果

ランダムグラフの辺の数を入力してください: 4
生成されたランダムグラフは次の通りです:
1-> { }
2-> { 8 }
3-> { 5 }
4-> { 孤立頂点！ }
5-> { 1 }
6-> { 孤立頂点！ }
7-> { 孤立頂点！ }
8-> { }
9-> { 孤立頂点！ }
10-> { 5 }

コードのポイント解説

• サイクルの検出： Checkcyclic() 関数は、新しい辺を追加しようとしたときにサイクルが発生するかどうかを再帰的に確認します。探索中にすでに訪問済みの頂点へ再度到達した場合はサイクルありと判断し、その辺の追加を拒否することで、常に非巡回（DAG）の状態を保ちます。
• 辺のランダム生成： rand()%N+1 によって 1〜10 の範囲の乱数を頂点番号として取得し、2つの頂点の間に辺を作成します。サイクルが検出されて破棄された場合は、別の乱数ペアで辺の生成をやり直します。
• 孤立頂点の判定： 出力処理では、どの辺にも接続されていない頂点（入次数・出次数がともに0の頂点）を「孤立頂点」として表示し、グラフの構造をひと目で把握できるようにしています。
• 計算量について： 辺を1つ追加するたびにサイクルチェックを実行するため、全体の時間計算量は O(e×v×e) となります。頂点数や辺の数が大きくなると処理に時間がかかるため、大規模なグラフを扱う場合はより効率的なアルゴリズム（例：トポロジカルソートを利用した手法）への置き換えを検討するとよいでしょう。