在有向圖中給出一個循環的例子

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的週期，那麼你只能說出所涉及的三個頂點，並且必須做一些調查以找到週期中其餘的頂點。

對於調查，您可以開始廣度優先搜索從父級開始的樹並查找訪問頂點，您應該可以通過這樣做來找到整個週期。