2

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

我刚刚阅读了Wikipedia 伪代码。

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是它可以回答上一个问题（链接问题）。对于LLsSCC 中的所有节点，将保证所有节点都相同。

4

3 回答 3

6

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

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

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

于 2014-06-09T05:42:36.810 回答
1

实际上，我想出了一种方法来检查 w 是否在 S 中或不在恒定时间内。只需有一个布尔字段inStack。

在将节点 w 推入堆栈时，制作w.inStack = true并在弹出它时，使其为假。

但第二个问题仍然存在。我们可以在不干扰算法的情况下进行轻微修改吗？

于 2014-06-09T05:42:23.967 回答
0

  1. 对于第二个问题，“我们可以做些细微的修改吗”，我猜你可以。因为lowlink值是向一个节点表明，没有更多未访问的邻居并且dfs index = lowlink，它是一个组件的根，因此可以弹出堆栈并打印。

    因此，对于一个组件节点，lowlink 值可以设置为大于或等于组件根的 dfs 索引的任何值。

于 2014-10-19T16:36:05.037 回答