我正在寻找一种使用 Ruby 获取树/网络模型所有可能路径的方法。
我的模型示例:
我需要的是所有可能路径的列表:
- 二次元
- 自动清算机
- 助理总干事
- ADH
- 开始
- 阿贝赫
- ABFG
- ABFH
每个节点都有一个子节点列表。子节点数可以是0..x
看起来很琐碎,但我还没有找到一种方法来做到这一点。有任何想法吗?提前致谢!
更新:
我设法得到了同样的结果:
def get_paths(ret_data, list = "")
children = get_children
list += description
if children.count == 0
ret_data.push(list)
end
children.each do |c|
c.get_paths(ret_data, list)
end
end
data = []
first_node.get_paths(data)
data ====>
[
"ACG",
"ACH",
"ADG",
"ADH",
"ABEG",
"ABEH",
"ABFG",
"ABFH"
]
结果正常,但是如果我在 get_paths 方法中将节点的描述推送到数组中,结果很奇怪:
def get_paths(ret_data, list = [])
children = get_children
list << description
if children.count == 0
ret_data.push(list)
end
children.each do |c|
c.get_paths(ret_data, list)
end
end
data = []
first_node.get_paths(data)
data ====>
[
[
"A",
"C",
"G",
"H",
"D",
"G",
"H",
"B",
"E",
"G",
"H",
"F",
"G",
"H"
],
[
"A",
"C",
"G",
"H",
"D",
"G",
"H",
"B",
"E",
"G",
"H",
"F",
"G",
"H"
],
[data like above],[data like above]....,
[
"A",
"C",
"G",
"H",
"D",
"G",
"H",
"B",
"E",
"G",
"H",
"F",
"G",
"H"
]]
number of paths ok (8), but data inside paths wrong
将节点的描述插入数组时会发生什么?
最佳答案
您应该发布一些代码来展示您的树是如何表示的。在这里,我只是发明了一种使用哈希的结构。
h={:name=>"H", :children=>[]}
g={:name=>"G", :children=>[]}
f={:name=>"F", :children=>[g,h]}
e={:name=>"E", :children=>[g,h]}
d={:name=>"D", :children=>[g,h]}
c={:name=>"C", :children=>[g,h]}
b={:name=>"B", :children=>[e,f]}
a={:name=>"A", :children=>[b,c,d]}
def paths(node,path='',&proc)
if node[:children].empty?
proc.call(path+node[:name])
else
node[:children].each{|c| paths(c,path+node[:name],&proc)}
end
end
paths(a){|path|
puts path
}
这是一个基本的深度优先搜索,跟踪到目前为止的路径并在叶节点上调用给定的 block 。
关于ruby - 如何获取树模型中所有可能的路径,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/22511920/