8

私は強結合成分に対する Tarjan のアルゴリズムを研究していますが、その仕組みは明らかです。とにかく、私が理解できない行があります：

// Consider successors of v
for each (v, w) in E do
  if (w.index is undefined) then
    // Successor w has not yet been visited; recurse on it
    strongconnect(w)
    v.lowlink  := min(v.lowlink, w.lowlink)
  else if (w.onStack) then
    // Successor w is in stack S and hence in the current SCC
    v.lowlink  := min(v.lowlink, w.index) // *************
  end if
end for

アスタリスクで線をマークしました。バックエッジに遭遇したときにノードの発見インデックス/時間を取得する必要があるのはなぜですか

v.lowlink  := min(v.lowlink, w.index)

コンポーネントの値を取得するだけでなく、

v.lowlink  := min(v.lowlink, w.lowlink)

これが問題になるケースは考えられません。

誰か教えてください。編集:これは単なるセマンティック要件であると思われます。つまり、 lowlink は、1 つの back-edge のみを持つノードから到達可能な最古の祖先として定義されていますが、これは単なる推測です。

4

1 に答える 1

5

w.lowlinkが少なくとも1 つのバック エッジwから到達可能な最低のインデックスであり、w最大でも 1 つのバック エッジを使用して到達可能な最低のインデックスである場合、正確性の証明は通過します。コンポーネント検出では、より低いインデックスに「エスケープ」できるかどうかを知る必要があります。

lowlinkおそらく、そのままの形で提示されているのは、ポストオーダーでしか設定されていないと想像できるため、バリエーションが明確に定義されないためです. (ウィキペディアの疑似コードは、事前に に初期化しindexます。)

于 2015-08-08T18:10:46.117 に答える