問題タブ [cycle-detection]

それぞれの長さの指定された量のサイクルを正確に含む有向グラフを生成したいと考えています。たとえば、グラフには次のものが含まれている必要があります。

• そのようなアルゴリズムはすでに存在しますか? そうでない場合、この問題を解決するためのあなたのアプローチは何ですか? 詳細には、次のパラメータが指定されています。

  1. 頂点の数 (例: 15)
  2. コンポーネントの数 (例: 2)
  3. グラフに含まれるサイクル (例: {3-cycle, 3-cycle, 5-cycle})

• 既存のグラフのサイクルを検出できるいくつかのアルゴリズム (Tarjan など) しか見つかりませんでした。サイクル検出アルゴリズムを使用して、特定の量のサイクルでグラフを生成することも可能だと思いますか?

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

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

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

誰かが有向/無向グラフでサイクルを検索するために BFS を使用して段階的な疑似コードを提供できますか?

O(|V|+|E|) の複雑さを得ることができますか?

これまでのところ、DFS の実装しか見たことがありません。