algorithm - さまざまなグラフ サイクル検出アルゴリズムを実験的にシミュレートして比較するにはどうすればよいですか?

Question

有向グラフのサイクル検出アルゴリズムは、増分ウェイ探索、強連結成分、BFS、双方向探索など、さまざまなアルゴリズムについて調べました。今度は、それをシミュレートしてパフォーマンスを比較したいと思います。エッジを挿入するたびにサイクル検出関数を呼び出しています。

ですから、私の質問は、どのような種類のデータセットを考慮すべきかということです。ランダム グラフを考えると、さまざまなアルゴリズムの評価基準は何になるでしょうか。一部のランダム グラフは巨大なサイズになる場合があります。しかし、それらは数回の反復でサイクルにつながる可能性があります。誰かがこれを行う方法を提案できると助かります。

また、パフォーマンスを比較するために、サイクルを削除してから再度挿入を続行することは理にかなっていますか。終了したら、すべての実装の実行時間を比較しますか?

Answer 1

これは、何のためにこれを行っているかによって大きく異なります。一般に、ランダム グラフを生成するアプローチは多数ありますが、おそらく最も有名なのはErdos-Renyiです。ただし、n 個の頂点を持つグラフがサイクルを持たないためには、最大で n - 1 個のエッジが必要であるため、このようなランダム グラフ ジェネレーターは高い確率でサイクルを持つことに注意してください。正確なケースによっては、グラフをできるだけまばらに保つことが最善である場合があります（つまり、エッジをほとんど許可しないでください）。