图论：python 中树中的路径

Question

邻接表（例如）：adj = [ [1,2],[2,3],[ ],[4],[ ] ] 假设图总是有向树

我需要进行路径递归并将每个路径存储在一个名为 full_path

的变量中

伪代码：

对于范围内的 i (0, len(adj), 1):

尽可能使用每条路径，直到到达死胡同
变量路径包含您刚刚访问过的节点，每次我们到达死胡同时重新初始化，在重新初始化之前我们将其保存为嵌套列表 full_path

对于我们的示例将给出：

0->1->2->[] 所以路径 = [0,1,2]
0->1->3->4->[] 所以路径 = [0,1,3,4]
0->2->[] 所以路径 = [0,2]
1->2->[] 所以路径 = [1,2]
1->3->4->[] 所以路径 = [1,3,4]
2->[] 所以路径 = [2]
3->4->[] 所以路径 = [3,4]
4->[] 所以路径 = [4]

因此 full_path = [ [0,1,2], [0,1,3,4], [0,2], [1,2], [1,3,4 ], [2], [3,4], [4] ]。这是函数必须提供的输出以符合教师的期望。 ('[ ]'表示已经到了死胡同)

for i in range(0,len(adj),1):
    for j in range(0,len(adj[i]),1):
        path += [i]
        current_node= j# , True
        a = len(adj[current_node])
        while a >0:      # to stop when a node leads to nowhere:  adj[j] = [] and so len(adj[j])==0
            for k in range(0,len(adj[current_node]),1):
                current_node = adj[current_node][k]
                path += [current_node]
                a = len(adj[current_node])
            final_path += [list(dict.fromkeys(path))]
            path = []

以上是我到目前为止所做的，但根本不起作用

Answer 1

最好在这个问题中使用 backtracking，因为使用有向树的问题具有递归性质。

adj = [ [1,2],[2,3],[ ],[4],[ ] ]

def getAllPath(adj):
  pathes = [] # list of all pathes reached <- what you want
  path = [] # to hold the current path
  def dfs(node):
    if not adj[node]: # if current node has no children
      pathes.append(path.copy()) # append a copy of current path to pathes
    else:
      for next_node in adj[node]:
        if next_node not in path: # if current node is not visited (useless if it's a directed tree)
          path.append(next_node) # push the next_node to the current path
          dfs(next_node)         # build the rest of the path
          path.pop()             # remove it from the path.
        
  for node in range(len(adj)): # loop over all nodes in the graph
    path.append(node) # add current start node to the path
    dfs(node)         # build the rest of the path
    path.pop()        # remove the start node
  return pathes

输出

[[0, 1, 2], [0, 1, 3, 4], [0, 2], [1, 2], [1, 3, 4], [2], [3, 4], [4]]

图论：python 中树中的路径

Graph theory: paths in a tree in python

python

graph-theory