algorithm - Tarjan 的算法 : Time Complexity and slight modification possibility

Question

这个问题与one recently asked here相关但不相同.

我刚刚阅读了 Wikipedia psuedocode .

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

显然我一定没有理解正确，因为我有两个非常基本的问题:

1. 当我们说 if (w is in S) 时，这不是 O(N) 或至少 O(logN) 复杂度的操作，因为元素应按它们的顺序排序指数？我们将不得不为每个可从根节点访问的新节点执行此操作，因此总体复杂度不是 O(NlogN)。此外，S 是一个堆栈，因此从概念上讲，只有顶部元素应该是可访问的，我们如何在其中实现搜索？二叉搜索树不应该是更好的数据结构吗？

2. 这部分:

   else if (w is in S) then
   v.lowlink := min(v.lowlink, w.index)

是否有使用 w.index 而不是 w.lowlink 的特定原因？使用 w.lowlink 的好处是它可以回答上一个问题(链接的问题)。 SCC 中所有节点的 LL 将保证所有节点都相同。

Answer 1

1) 你的第一个问题:O(1) 可以很容易地完成，只需要维护一个 bool 数组inStack，节点n 被放入堆栈的那一刻, 将 inStack[n] 标记为 true。当您将其从堆栈中弹出时，将其标记回 false。

2) w.index 和 w.lowlink 之间没有太大区别，但这更容易阅读，因为我们将理解这个条件是检查来自节点 A ->B ->C ->A 的情况，检查节点 C 何时可以到达前任节点 A。请记住，在我们更新 C 的那一刻，节点 A lowlink 尚未正确更新。

Tarjan 算法基于这样一个事实，即一个节点将成为 SCC 的根当且仅当从该节点我们无法到达任何前任节点(这意味着它在其 SCC 中具有最低的低链路并且也等于该节点的索引)。所以条件只是以最直接的方式实现了这个想法，如果我们遇到一个已经访问过的节点，我们检查这个节点是否是当前节点的前驱(这由它的索引决定，也是级别图中的这个节点)