循環有向グラフがあります。リーフから始めて、各ノードに接続されているデータを、そのノードから到達可能なすべてのノードに下流に伝播したいと思います。特に、サイクルが安定するまで、到達したサイクルの前後でデータをプッシュし続ける必要があります。
これはストックグラフの走査問題であると完全に確信しています。ただし、適切なアルゴリズムを見つけるのにかなり苦労しています---いくつかの重要な検索キーワードが欠落していると思います。
私が自分の半ばのO（n ^ 3）アルゴリズムを書き込もうとする前に、誰かが私に適切な解決策を教えてもらえますか？そして、この特定の問題は何と呼ばれていますか？
グラフは循環的であるため（つまり、循環を含めることができる）、最初にグラフを強く連結されたコンポーネントに分解します。有向グラフの強連結成分は、各ノードが同じサブグラフ内の他のすべてのノードから到達可能であるサブグラフです。これにより、一連のサブグラフが生成されます。複数のノードの強く接続されたコンポーネントは、事実上サイクルであることに注意してください。
これで、各コンポーネントで、1つのノードの情報は、最終的にグラフの他のすべてのノードに到達します（すべて到達可能であるため）。したがって、サブグラフごとに、その中のすべてのノードからすべてのデータを取得し、すべてのノードに同じデータセットを持たせることができます。サイクルを続ける必要はありません。また、このステップの最後に、同じコンポーネント内のすべてのノードにまったく同じデータが含まれます。
次のステップは、強く接続された各コンポーネントを単一のノードに折りたたむことです。同じコンポーネント内のノードはすべて同じデータを持ち、したがって基本的に同じであるため、この操作は実際にはグラフを変更しません。新しく作成された「スーパーノード」は、コンポーネントの外部のノードからコンポーネントのノードに出入りするすべてのエッジを継承します。
強く連結されたすべてのコンポーネントを折りたたんだため、結果のグラフにはサイクルがありません（結果のノードによって形成されたサイクルがあった場合、そもそもそれらはすべて同じコンポーネントに配置されていたはずです）。結果のグラフは、有向非巡回グラフになります。サイクルはなく、indegree = 0のすべてのノード（つまり、入力エッジのないノード）からの単純な深さ優先探索で、各ノードから隣接するノード（つまり「子」）にデータを伝播する必要があります。 。