有向グラフのサイクルの例を与える

Question

有向グラフ内に1つのサイクルインスタンスを与えるアルゴリズムが必要です。誰かが私に方向性を示すことができますか？擬似コードで、または好ましくはRubyで？

私は先にa similar questionと尋ねてきましたが、そこに提案されているとおり、グラフにサイクルがあるかどうかを検出するKahnのアルゴリズムを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]] 

私は検査の終了時に上記のコードで出力する変数た場合、それは与える：

#=> [[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]] 

あり、これらのコンポーネントを選択することで長いものよりも、Iは、サイクルを得る：

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のサイクルであれば、関与する3つの頂点だけを伝えることができ、サイクル中の残りの頂点を見つけるために何らかの調査を行わなければならないことです。

調査のために、親から始めて訪問先の頂点を探して、幅広い最初の検索を開始することができます。そうすることで、全体のサイクルを見つけることができます。