巡回有向グラフのトラバーサル

Question

Iは、環状有向グラフを有しています。葉から開始し、私はそのノードから到達可能なすべてのノードに下流の各ノードに接続されたデータを伝播したいです。特に、私はサイクルが安定するまで達している任意のサイクルを中心にデータをプッシュし続ける必要があります。

私は、これは株式グラフトラバーサルの問題であることを完全に確信しています。しかし、私はいくつかの重要な検索キーワードが欠けていると思う---適切なアルゴリズムを見つけようと難易度の公平なビットを持っています。

私は適切な解決策で自分の中途半端O（N ^ 3）アルゴリズム、缶誰ポイント私を書き込もうとする前に？そして、何<私>がこの特定の問題と呼ばれる？

Answer 1

グラフ（すなわちサイクルを含むことができる）環状であるので、

は、私が最初の強連結成分にそれを打破することになります。有向グラフのA 強連結成分には、各ノードが内のすべての他のノードから到達可能であるサブグラフであります同じサブグラフ。これは、部分グラフのセットをもたらすであろう。複数のノードの強連結成分を効果的サイクルであることに注意してください。

（これらは全て到達可能であるので）

次に、各成分において、一つのノード内の情報は、最終的に、グラフの他のすべてのノードに終わるであろう。したがって、各部分グラフのために私たちは、単にその中のすべてのノードからすべてのデータを取得し、すべてのノードが同じデータセットを持つことができます。サイクルを続けるする必要はありません。また、このステップの終了時に、同じコンポーネント内のすべてのノードが正確に同じデータを含んでいます。

次のステップは、単一のノードに各強連結成分を縮小することであろう。同じコンポーネント内のノードはすべて同じデータを持っているので、基本的に同じであるように、この操作は実際にグラフを変更しません。新しく作成された「スーパーノード」は、すべてのエッジが外出やコンポーネント外のノードから構成要素のノードに入ってくる継承されます。

私たちは、すべての強連結成分を崩壊したので、結果のグラフに何のサイクルは存在しません（そこに結果のノードによって形成されたサイクルされていたので、なぜ？、彼らはすべての最初の場所で同じ構成要素に置かれていたであろう）。結果のグラフは現在、有向非循環グラフです。そこにはサイクルがありません、そして0（すなわち、ノード着信エッジを持っていないこと）、その隣接ノードに各ノードからのデータを伝播する（すなわちその「子供」）は、仕事を得る必要があります=入次数を持つすべてのノードからの単純な深さ優先走査ます。