如何使用Ruby在圖形中查找連接的組件

查找圖形的連接組件的最簡單方法是什麼？ 不牢固連接的組件可以在TSort模塊中找到。如何使用Ruby在圖形中查找連接的組件

有一個庫RGL它有一個方法在模塊RGL::Graph::each_connected_component，但如何建立一個圖並調用此圖的方法？

我創建樣本圖表等

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

，並希望找到它的連接部件，其是[[1,2,3]，[4,5]，但沒有方法each_connected_component在g

class RGL::DirectedAdjacencyGraph 
    include RGL::Graph 
end

沒有幫助。

來源

2014-01-08 s9gf4ult

該寶石有文檔：http://rgl.rubyforge.org/rgl/index.html - 你看過嗎？如果是這樣，你能解釋一下，使用一些代碼片段，你卡在哪裏？ –

我用'RGL :: DirectedAdjacencyGraph.new'創建了圖形，不知道下一步該怎麼做。 – s9gf4ult

看來你可能只需要'需要'rgl/connected_components''但是，'each_connected_component'只適用於無向圖。你需要一個有向圖嗎？ –

兩件事情，這可能有助於（警告：我不知道這種寶石良好，有可能是更好的方法）

您需要添加一個要求，以使可用的方法：require 'rgl/connected_components'
each_connected_component假設無向圖，但如有必要，可以

釷有向圖轉換爲無向一個e下面的代碼似乎做你想做的事：

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

來源

2014-01-08 16:32:28

如何使用Ruby在圖形中查找連接的組件

回答

相關問題