2

この質問は関連していますが、最近質問されたものと同じではありませんhere .

ウィキペディアの疑似コードを読んだところです。

algorithm tarjan is
  input: graph G = (V, E)
  output: set of strongly connected components (sets of vertices)

  index := 0
  S := empty
  for each v in V do
    if (v.index is undefined) then
      strongconnect(v)
    end if
  end for

  function strongconnect(v)
    // Set the depth index for v to the smallest unused index
    v.index := index
    v.lowlink := index
    index := index + 1
    S.push(v)

    // 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 is in S) then
        // Successor w is in stack S and hence in the current SCC
        v.lowlink  := min(v.lowlink, w.index)
      end if
    end for

    // If v is a root node, pop the stack and generate an SCC
    if (v.lowlink = v.index) then
      start a new strongly connected component
      repeat
        w := S.pop()
        add w to current strongly connected component
      until (w = v)
      output the current strongly connected component
    end if
  end function

2 つの非常に基本的な質問があるため、明らかに適切に理解していなかったに違いありません。

  1. と言うときif (w is in S)、要素はインデックスによって順序付けられるため、この操作は O(N) または少なくとも O(logN) の複雑さではありませんか? ルート ノードからアクセスできる新しいノードごとにこれを実行する必要があるため、全体的な複雑さはありませんO(NlogN)。さらに、S はスタックであるため、概念的には最上位の要素のみにアクセスできる必要があります。その中で検索を実装するにはどうすればよいでしょうか? ここでは、二分探索木の方が優れたデータ構造であるべきではありませんか?

  2. この部分では:

    そうでなければ (w は S にある) then
    v.lowlink := min(v.lowlink, w.index)

w.indexand notを使用する特定の理由はありw.lowlinkますか? 使用する利点はw.lowlink、前の質問 (リンクされた質問) に回答できることです。SCC 内のLLsすべてのノードの は、すべてのノードで同じであることが保証されます。

4

3 に答える 3

6

1) 最初の質問: O(1) で簡単に実行できます。ブール配列inStackを維持するだけで、ノードがスタックに置かれた瞬間に truenにフラグが設定inStack[n]されます。スタックからポップしたら、フラグを false に戻します。

2) と の間に大きな違いはありませんw.indexがw.lowlink、この条件はノード A -> B -> C -> A のケースをチェックすることであり、ノード C がいつ先行ノードに到達できるかをチェックすることであることが理解できるため、読みやすくなっています。ノードAかどうか。C を更新する時点では、ノード A のローリンクはまだ適切に更新されていないことに注意してください。

Tarjan アルゴリズムは、ノードが SCC のルートになるという事実に基づいているのは、そのノードから先行ノードに到達できない場合のみです (つまり、SCC に最低のローリンクがあり、このノードのインデックスに等しいことを意味します)。 ）。したがって、条件はこのアイデアを最も単純な方法で実装しただけです。既にアクセスされているノードに遭遇した場合、このノードが現在のノードの先行ノードであるかどうかを確認します (これは、そのインデックスによって決定され、レベルによっても決定されます)。グラフ内のこのノードの)

于 2014-06-09T05:42:36.810 に答える
1

実際、私は w が S にあるか一定時間にないかをチェックする方法を見つけました。単純に boolean フィールドを持っていますinStack。

ノード w をスタックにプッシュしている間は makew.inStack = trueし、ポップしている間は false にします。

しかし、2 つ目の疑問はまだ残っています。アルゴリズムを乱すことなく、わずかな変更を加えることができますか?

于 2014-06-09T05:42:23.967 に答える
0

  1. 2 番目の質問である「わずかな変更を加えることができますか」については、できると思います。lowlink の値は、未訪問のネイバーがなくなり、dfs index = lowlink を持つノードに対して、それがコンポーネントのルートであることを示し、スタックをポップして出力できることを示します。

    したがって、コンポーネント ノードの lowlink 値は、コンポーネント ルートの dfs インデックス以上の任意の値に設定できます。

于 2014-10-19T16:36:05.037 に答える