ruby - 如何获取树模型中所有可能的路径

Question

我正在寻找一种使用 Ruby 获取树/网络模型所有可能路径的方法。

我的模型示例:

我需要的是所有可能路径的列表:

1. 二次元
2. 自动清算机
3. 助理总干事
4. ADH
5. 开始
6. 阿贝赫
7. ABFG
8. 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

将节点的描述插入数组时会发生什么？

Answer 1

您应该发布一些代码来展示您的树是如何表示的。在这里，我只是发明了一种使用哈希的结构。

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 。