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

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

我之前问了一个类似的问题 ，并按照那里的建议，我在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]] 

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

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

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

Answer 1

我在math 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]]] 

Answer 2

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

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