Tarjan 算法：时间复杂度和轻微修改的可能性

Question

这个问题与最近在这里提出的问题有关但又不同。

我刚刚阅读了维基百科伪代码。

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是它可以回答上一个问题（链接问题）。将LLs在SCC所有节点将保证是相同的所有节点。

Answer 1

1）您的第一个问题：它可以在 O(1) 中轻松完成，只需维护一个布尔数组inStack，将节点n放入堆栈的那一刻，标志inStack[n]为真。当您将其从堆栈中弹出时，将其标记回 false。

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

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