algorithm - 在邻接列表中查找路径

Question

查找邻接列表的两个节点之间的所有路径的最佳算法是什么

示例输入：

source = 1
destination = 5
list = {1: [2], 2: [4], 3: [4, 5], 4: [5]}

标签： algorithm

Answer 1

def paths(adj, st, en)
  return [] unless adj.key?(st)
  adj[st].each_with_object([]) do |nxt,arr|
    nxt == en ? arr << [st, en] :
      paths(adj, nxt, en).each { |a| arr << [st, *a] }
  end
end

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

请注意，我添加了一个隔离节点8。

paths(adj, 1, 7)
  #=> [[1, 2, 4, 5, 7],
  #    [1, 2, 4, 6, 7],
  #    [1, 2, 7],
  #    [1, 3, 4, 5, 7],
  #    [1, 3, 4, 6, 7]]