在有向图中给出一个循环的例子

Question

我想要一个算法，如果有的话在有向图中给出一个循环的一个实例。任何人都可以告诉我一个方向？在伪代码中，或者最好在Ruby中？

我以前问过a similar question，并且按照那里的建议，我在Ruby中实现了Kahn的算法，它检测一个图是否有一个循环，但我不仅想要它是否有循环，而且还想要这样循环的一个可能的实例。

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]] 

如果我在考试结束上面的代码输出变量，它会给：

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

，其中包括我想要的周期，但它也包括额外的边缘不相关的周期。

Answer 1

我在the math stackexchange site问了同样的问题，并得到了答案。事实证明，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]]] 

Answer 2

深度第一次搜索，在那里你跟踪访问的顶点和父母会给你的周期。如果您看到以前访问过的顶点的边缘，那么您已经检测到您的父母，您自己和该顶点之间的循环。你可能遇到的一个小问题是，如果它是一个长度大于3的周期，那么你只能说出所涉及的三个顶点，并且必须做一些调查以找到周期中其余的顶点。

对于调查，您可以开始广度优先搜索从父级开始的树并查找访问顶点，您应该可以通过这样做来找到整个周期。