Tarjan算法的Ruby版本中的Bug

Question

http://en.wikipedia.org/wiki/tarjan's_strongly_connected_components_algorithm

http://en.algoritmy.net/article/44220/tarjans-算法

我无法在我的Ruby版本的Tarjan算法中找出这个bug用于强连接组件。我得到了Kosaraju-Sharir算法，我的Tarjan算法在Ruby中适用于一些图。但它没有连接两个应该连接的组件--“10”和“11、12、9”

输入文件是这个有向图:http://algs4.cs.princeton.edu/42directed/tinydg.txt

expected: [["1"], ["0", "2", "3", "4", "5"], ["10", "11", "12", "9"], ["6", "8"], ["7"]]
got: [["1"], ["0", "2", "3", "4", "5"], ["10"], ["11", "12", "9"], ["6", "8"], ["7"]]

在这个尝试创建单个组件的最后一个循环中，它以“10”（堆栈上的最后一项）开始，但随后当前顶点（“父”）也是“10”！这使得循环切断“10”作为一个单独的组件。为什么堆栈上的最新项与父节点相同？我希望“10”只会出现在组件的末尾，在我们收集了[“12”，“11”，“9”...然后是“10”]之后。因为“10”首先出现，而不是最后出现，所以我们有这个问题。我怎么修好它？

  begin
    last_stack_item = stack.pop
    component << last_stack_item.name
  end while last_stack_item != parent # we're back at the root

我的Ruby代码：

    # Tarjan's algorithm to find all strongly connected components (SCCs)
    def scc_tarjan
      index = 0 # numbers nodes consecutively in the order discovered
      stack, scc, vertices = [], [], []

      # create new Struct, if not already defined
      if Struct::const_defined?("TarjanVertex")
        Struct.const_get("TarjanVertex")
      else
        Struct.new("TarjanVertex", :name, :index, :lowlink)
      end

      adj_lists.each do |v|
        # -1 means vertex is unvisited
        vertex = Struct::TarjanVertex.new(v.name, -1, -1)
        vertices << vertex  # array of all TarjanVertex objects in graph
      end
      vertices.each do |vertex|
        tarjan_dfs(vertex, scc, stack, index, vertices) if vertex.index == -1
      end
      # return nested array of all SCCs in graph
      scc
    end

  def tarjan_dfs(parent, scc, stack, index, vertices)
    # Set depth index for vertex to smallest unused index
    parent.index = index
    # lowlink is roughly the smallest index of any node known to be reachable from the vertex
    parent.lowlink = index
    index += 1
    stack << parent
    # loop through all vertices connected to parent
    adj_vertices(parent.name, adj_lists).each do |adj_vertex|
      # since adj_vertices returns array of strings,
      # must convert to TarjanVertex objects
      child = vertices.select {|v| v.name == adj_vertex}.first

      if child.index == -1  # if child vertex not yet visited
        tarjan_dfs(child, scc, stack, index, vertices) # recurse on child

        # change parent's lowlink to smaller lowlink of parent and child)
        parent.lowlink = [parent.lowlink, child.lowlink].min

      # vertex points to earlier (already visited) one in stack,
      # with lower index. thus it's the current SCC
      elsif stack.include?(child)
        parent.lowlink = [parent.lowlink, child.index].min
      end
    end

    # if a vertex's lowlink = its index here, this # cannot go any lower.
    # vertex MUST be root of the SCC.
    if parent.lowlink == parent.index
      component = []  # a single SCC

      # pop off entire SCC, one vertex at a time
      begin
        last_stack_item = stack.pop
        component << last_stack_item.name
      end while last_stack_item != parent # we're back at the root
      scc << component.sort # done with a single SCC
    end
  end

Answer 1

我解决了自己的问题！在用笔和纸检查了代码的每个循环之后，我发现它过早地进入了顶点4的底部组件循环。此时Parent.LowLink不应等于Parent.Index。我只需要修改一个词就能解决我的问题！

我在“elsif stack.include？（child）”循环中将“child.index”更改为“child.lowlink”！这正确地删除了4的下链接，以匹配顶点6的下链接。

从那时起，parent.lowlink！=parent.index，它不会过早地开始创建新组件。

有趣的是，我的解决方案不同于我在Tarjan算法上找到的所有伪代码和在线代码，它们都说“parent.lowlink=[parent.lowlink,child.index].min”

相反，我需要“parent.lowlink=[parent.lowlink,child.lowlink].min”