6

ノードの値を隣接ノードf(n)の各値の関数として更新/計算するグラフ アルゴリズムを作成したいと考えています。f(n)

  • グラフに向きがあります。
  • 各ノードには初期値として f(n) 値があります。
  • 各エッジにはコストがありません (0)。
  • 各ノードの値は、その現在の値と各隣接ノードの値の最大値です (有向グラフなので、隣接ノードは、ノードが着信エッジを持つ場所からのものです)。

より正式には、

f(n) = max(f(n),max_i(f(n_i))), where i from neighbor 1 to neighbor k.

そうするためのいくつかの方法を視覚化できますが、それらがどの程度最適かはわかりません。

誰か提案や解説をお願いできますか (あなたの提案が最適だと思いますか)、または私が適応できる既存のグラフアルゴリズムを提案できますか?

4

1 に答える 1

6

請求：

  1. グラフの各強連結成分 Vでは、この SCC のすべての頂点の値が同じ最終スコアになります。
    「証明」(ガイドライン): この SCC で伝播を行うことにより、すべてのスコアをこの SCC で見つかった最大値に繰り返し設定できます。

  2. DAGでは、各頂点の値はmax{v,parent(v) | for all parents of v}(定義) であり、スコアは開始から終了までの 1 回の反復内で見つけることができます。
    「証明」（指針）：「裏辺」がないので、すべての親の最終値がわかれば、各頂点の最終値がわかります。帰納法 (ベースはすべてのソース) - 最終スコアを決定するには 1 回の反復で十分であるという事実に到達できます。

  3. G'また、グラフのＳＣＣを表すグラフgがＤＡＧであることも知られている。

上記から、単純なアルゴリズムを導き出すことができます。

  1. グラフ内の最大 SCC を検索し ( Tarjan アルゴリズムで実行できます)、SCC グラフを作成します。ましょうG'。G'DAGであることに注意してください。
  2. 各 SCC に対してV: 設定しますf'(V) = max{v | v in V}(直感的に - 各 SCC の値をこの SCC の最大値として設定します)。
  3. グラフをトポロジカルに並べ替えG'ます。
  4. (3) で見つかったトポロジカル ソートに従って 1 回トラバーサルを実行G'し、親に従って各頂点の f'(V) を計算します。
  5. 設定f(v) = f'(V)(v は SCC V 内)

複雑：

  1. タージャンと作成G'はO(V+E)
  2. f' を見つけることも、グラフのサイズに線形です -O(V+E)
  3. トポロジカルソートが実行されますO(V+E)
  4. シングル トラバーサル - 線形:O(V+E)
  5. 最終スコアを与える: 線形!

したがって、上記のアルゴリズムはグラフのサイズに線形です-O(V+E)

于 2012-10-24T16:24:17.223 に答える