5

有向グラフにサイクルのインスタンスがあれば、それを与えるアルゴリズムが必要です。誰か私に方向性を教えてもらえますか？擬似コードで、またはできればRubyで？

以前に同様の質問をし、そこでの提案に従って、グラフにサイクルがあるかどうかを検出するカーンのアルゴリズムをRubyに実装しましたが、サイクルがあるかどうかだけでなく、そのようなサイクルの1つの可能なインスタンスも必要です。

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

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を超えるサイクルの場合、関係する3つの頂点しか認識できず、サイクル内の残りの頂点を見つけるために調査を行う必要があることです。

調査のために、親から始めてツリーを「上へ」幅優先探索を開始し、訪問した頂点を探すことができます。これを行うことで、サイクル全体を見つけることができるはずです。

于 2012-03-15T22:38:26.133 に答える