Ruby-从给定的起点查找通过图的所有路径

Question

散列图填充如下：

{"1"=>["2"], "2"=>["3", "7"], "3"=>["4"], "5"=>["6", "2"], "6"=>["7"], "7"=>["8", "4"]}

，以便每个键可以具有多个值。这些值代表一组路线上的公交车站，例如从公交车站1可以到达2，从公交车站2可以到达3或7，依此类推。

我正在尝试遍历此图形结构，并从给定的起点查找所有可能的路径。例如，对于起点1，所有可能路径的列表将为

[[1,2] , [1,2,3] , [1,2,3,4] , [1,2,7] , [1,2,7,8], [1,2,7,4]]

我试图递归地解决此问题，在该迭代中，对当前键的子级（该键的值）进行迭代，并调用一个实质上扩展该键的子级的函数。到目前为止，这是我的代码：

if hash.has_key?(origin.to_s)
  tmp = origin.to_s
  tmp << hash[origin.to_s][0]
  paths.push(tmp)
  expand_node(hash,paths,paths.length-1,tmp[tmp.length-1])
end

来源是起点。首先，我将第一个路径（在这种情况下为[1,2]）添加到名为paths的数组中，然后展开添加到前一个路径（在这种情况下为2）的最后一个值。

def expand_node(hash,paths,curr_paths_index,node)
curr_node = node
if hash.has_key?(node.to_s)
  counter = 0
  hash[curr_node].each do |child|
    tmp = paths[curr_paths_index]
    tmp << child
    paths << tmp
    curr_paths_index += counter + 1
    puts paths
    expand_node(hash,paths,curr_paths_index,child)
  end
end
结束

参数curr_paths_index跟踪我展开的路径。参数path是当前找到的路径的整个列表。参数node是正在扩展的当前值。

功能完成后打印paths将产生：

123
123
1234
1234
1234
12347
12347
12347
12347
123478
123478
123478
123478
123478
1234784
1234784
1234784
1234784
1234784
1234784

有什么方法可以修改此代码，以便产生所需的输出（如上所示）？总的来说，有没有更好的方法来解决这个问题？

谢谢。

散列图填充如下：{“ 1” => [“ 2”]，“ 2” => [“ 3”，“ 7”]，“ 3” => [“ 4”]，“ 5 “ => [” 6“，” 2“]，” 6“ => [” 7“]，” 7“ => [” 8“，” 4“]}，这样每个键可以有多个值。这些值...

Answer 1

我会这样做，很确定可以进一步优化它，并且性能也可能有问题。

Answer 2

解决递归问题的一种方法是先将其分解为易于解决的单个案例，然后将其归纳为一个案例。这是一个简单的情况：

Answer 3

def doit(graph, start)
  return [] unless graph.key?(start)
  recurse(graph, start)
end

def recurse(graph, start)
  (graph[start] || []).each_with_object([[start]]) { |next_node, arr|
    recurse(graph, next_node).each { |a| arr << [start, *a] } }
end