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

Question

我希望有一个算法，如果有的话，可以在有向图中给出一个循环实例。 有人能指导我吗？最好用伪代码或Ruby。

我之前问过类似的问题，并根据那里的建议，在Ruby中实现了Kahn算法来检测图中是否有循环，但我不仅想知道它是否有循环，还想知道其中一个可能的循环实例。

example_graph = [[1, 2], [2, 3], [3, 4], [3, 5], [3, 6], [6, 2]]

Kahn算法

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

这段内容包含我想要的循环部分，但也包含与循环无关的额外边缘。

- sawa

Answer 1

我在数学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]]]

- sawa

Answer 2

深度优先搜索，其中需要跟踪访问过的顶点和父节点，这将给您提供循环。如果您看到一条边到达先前访问过的顶点，则在您的父节点，自己和该顶点之间检测到一个循环。您可能会遇到的一个小问题是，如果是长度大于3的循环，您只能告诉涉及到的三个顶点，并且必须进行一些调查来找出循环中其余的顶点。

对于调查，您可以从父节点开始启动一次广度优先搜索并寻找访问过的顶点，通过这样做，您应该能够找到整个循环。

- Justin