反復DFSで有向グラフのサイクルを検出する方法は？

Question

私の現在のプロジェクトには、入力と出力を持つノードのセットがあります。各ノードは、その入力値を取り、いくつかの出力値を生成することができる。これらの出力は、他のノードの入力として使用できます。必要な計算量を最小限に抑えるため、ノードの依存関係はアプリケーションの開始時にチェックされます。ノードを更新するとき、それらは互いに依存する逆の順序で更新されます。

つまり、ノードはの有向グラフに似ています。私は、反復DFS（巨大なグラフのスタックオーバーフローを回避する再帰はありません）を使用して依存関係を解き、ノードを更新するための順序を作成しています。

さらに、グラフの循環を避けたいのは、循環依存がアップデータアルゴリズムを壊し、永久に実行ループを引き起こすためです。

再帰スタック上のノードを追跡することによってDFSでサイクルを見つける再帰的なアプローチがありますが、には繰り返し実行する方法があります？私はその後、主依存関係リゾルバにサイクル検索を埋め込んで、処理速度を上げることができました。

Answer 1

タイムスタンプを試してください。メタタイムスタンプを追加し、ノードでゼロに設定します。

前の回答（非該当）：

あなたが検索、増分または時間をつかむ（）スタンプを開始します。次に、 ノードにアクセスした場合は、現在の検索タイムスタンプと比較します。 が同じ場合は、サイクルが見つかりました。そうでなければ、スタンプ を最新の状態に設定します。

次の検索では、再び増分します。

• は、（検索用）スタックおよび（更新用）のベクトルにルートノードを追加します。

[OK]を、これは私はあなたがあなたのDFSの検索を実行していると仮定しています方法です。

スタックをポップし、スタックが

空になるまで逆方向（子ノードを参照することによって）

をベクターと更新値を反復スタックおよびベクター

ループに現在のノードの子を追加問題：サイクルによって、同じノードセットがスタックに追加されます。

解決方法1：ブール値/タイムスタンプを使用して、DFS検索スタックに追加する前にノードが訪問されているかどうかを確認します。これはサイクルを排除しますが、それらは解決しません。エラーを吐き出して終了することができます。

解決方法2：タイムスタンプを使用しますが、スタックをポップするたびに増分します。子ノードにタイムスタンプセットがあり、それが現在のスタンプよりも小さい場合は、サイクルが見つかりました。キッカーがあります。値を逆方向に反復するとき、子ノードのタイムスタンプをチェックして、それらが現在のノードよりも大きいかどうかを確認できます。それ以下であれば、サイクルが見つかりましたが、デフォルト値を使用できます。

実際、ソリューション1は、値を更新して起動時にすべてのノードをデフォルト値に設定するときに、複数の子を続行しないように同じ方法で解決できると思います。ソリューション2はグラフの評価中に警告を表示しますが、ソリューション1ではベクトルの作成時に警告が表示されます。

Answer 2

オンラインでは、多くのサイクル検出アルゴリズムが利用できます。最も簡単なものは、Dijkstraのアルゴリズムの拡張バージョンです。訪れたノードのリストとそこに到達するためのコストを維持します。あなたの設計では、 "コスト"をパスに置き換えてそこに行きます。

アルゴリズムの各反復では、「アクティブ」リスト上の次のノードを把握し、グラフ内のそれに続く各ノード（つまりそれぞれの依存関係）を調べます。そのノードが「visited」リストにある場合は、サイクルがあります。あなたがここにいることを維持しているpathは、ループパスを示しています。

移動するには十分ですか？