5

我想要一种算法，如果有的话，它会在有向图中给出一个循环实例。谁能告诉我一个方向？在伪代码中，或者最好是在 Ruby 中？

我之前问过一个类似的问题，并按照那里的建议，我在 Ruby 中实现了卡恩算法，该算法检测图是否有循环，但我不仅想要它是否有循环，还想要这种循环的一个可能实例。

example_graph = [[1, 2], [2, 3], [3, 4], [3, 5], [3, 6], [6, 2]]

卡恩算法

def cyclic? graph
  ## The set of edges that have not been examined
  graph = graph.dup
  n, m = graph.transpose
  ## The set of nodes that are the supremum in the graph
  sup = (n - m).uniq
  while sup_old = sup.pop do
    sup_old = graph.select{|n, _| n == sup_old}
    graph -= sup_old
    sup_old.each {|_, ssup| sup.push(ssup) unless graph.any?{|_, n| n == ssup}}
  end
  !graph.empty?
end

上面的算法告诉一个图是否有循环：

cyclic?(example_graph) #=> true

但我不仅想要这样的循环示例：

#=> [[2, 3], [3, 6], [6, 2]]

如果我在检查结束时输出上述代码中的变量graph，它将给出：

#=> [[2, 3], [3, 4], [3, 5], [3, 6], [6, 2]]

其中包括我想要的循环，但它也包括与循环无关的额外边缘。

4

2 回答 2

5

我在数学 stackexchange 网站上问了同样的问题，并得到了答案。事实证明，Tarjan 的算法很好地解决了这个问题。我在Ruby中实现它如下：

module DirectedGraph; module_function
    ## Tarjan's algorithm
    def strongly_connected_components graph
        @index, @stack, @indice, @lowlink, @scc = 0, [], {}, {}, []
        @graph = graph
        @graph.flatten(1).uniq.each{|v| strong_connect(v) unless @indice[v]}
        @scc
    end
    def strong_connect v
        @indice[v] = @index
        @lowlink[v] = @index
        @index += 1
        @stack.push(v)
        @graph.each do |vv, w|
            next unless vv == v
            if !@indice[w]
                strong_connect(w)
                @lowlink[v] = [@lowlink[v], @lowlink[w]].min
            elsif @stack.include?(w)
                @lowlink[v] = [@lowlink[v], @indice[w]].min
            end
        end
        if @lowlink[v] == @indice[v]
            i = @stack.index(v)
            @scc.push(@stack[i..-1])
            @stack = @stack[0...i]
        end
    end
end

因此，如果我将其应用于上面的示例，我会得到一个图的强连通分量列表：

example_graph = [[1, 2], [2, 3], [3, 4], [3, 5], [3, 6], [6, 2]]
DirectedGraph.strongly_connected_components(example_graph)
#=> [[4], [5], [2, 3, 6], [1]]

通过选择那些长于一个的组件，我得到了循环：

DirectedGraph.strongly_connected_components(example_graph)
.select{|a| a.length > 1}
#=> [[2, 3, 6]]

此外，如果我从图中选择两个顶点都包含在组件中的边，我会得到构成循环的关键边：

DirectedGraph.strongly_connected_components(example_graph)
.select{|a| a.length > 1}
.map{|a| example_graph.select{|v, w| a.include?(v) and a.include?(w)}}
#=> [[[2, 3], [3, 6], [6, 2]]]
于 2012-03-16T05:16:08.513 回答
2

深度优先搜索，您可以在其中跟踪访问的顶点，父节点将为您提供循环。如果您看到之前访问过的顶点的边，那么您已经检测到您的父母、您自己和该顶点之间的循环。您可能会遇到的一个小问题是，如果它是一个长度 > 3 的循环，您将只能分辨出所涉及的三个顶点，并且必须进行一些调查以找到循环中的其余顶点。

对于调查，您可以从父级开始“向上”搜索树并查找访问的顶点，您应该能够通过这样做找到整个循环。

于 2012-03-15T22:38:26.133 回答