ruby - 如何使用 Ruby 在图中查找连通分量

Question

找到图的连通分量最简单的方法是什么？ 非强连通分量可以通过TSort模块找到。

RGL 库在 RGL::Graph::each_connected_component 模块中有一个方法，但是如何构建一个图并为这个图调用这个方法呢？

我已经创建了示例图，例如

g = RGL::DirectedAdjacencyGraph[1,2, 2,3, 4,5]

并且想找到它的连通分量，它们是 [[1,2,3],[4,5]] 但是 g 中没有方法 each_connected_component

class RGL::DirectedAdjacencyGraph
  include RGL::Graph
end

没有帮助。

Answer 1

有两件事可能会有所帮助(注意:我不太了解这个 gem，可能有更好的方法)

• 您需要添加一个 require 才能使该方法可用:require 'rgl/connected_components'

• each_connected_component 假定一个无向图，但您可以根据需要将有向图转换为无向图

下面的代码似乎可以满足您的要求:

require 'rgl/base'
require 'rgl/adjacency'
require 'rgl/connected_components'

g = RGL::DirectedAdjacencyGraph[1,2, 2,3, 4,5]

components = []

g.to_undirected.each_connected_component { |c| components <<  c }

p components

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