如何用Python递归函数从指定字典生成完整目标路径序列？

需求说明 #

输入节点关联字典（示例：{1: [2, 6], 2: [3], 6: [5], 3: [4], 5: [8, 9], 4: [5, 7]}），生成所有从起始节点1到叶子节点的完整路径序列。目标输出为[[1,2,3,4,5,8],[1,2,3,4,5,9],[1,2,3,4,7],[1,6,5,8],[1,6,5,9]]。
路径生成逻辑：从节点1出发，若路径最后一个元素是字典的键，则将该键对应的每个值分别追加到路径中生成新分支，直到路径末尾为无后续节点的叶子节点。

现有问题 #

1. 自行编写的递归函数陷入无限循环，代码如下：

lists = []
lines = {1: [2, 6], 2: [3], 6: [5], 3: [4], 5: [], 4: [5,7]}
def create_lines(cont=False):
    for k,val in lines.items():
        print(lists)
        for l in lists:
            if k==l[-1]:
                if lines[k]:
                    l.append(lines[k][0])
                    cont=True
                    break
        if cont:               
            continue

        for v in val:
            lists.append(list([k,v]))
            cont=False
    for l in lists:
        print("second loop")
        if l[-1] in lines and lines[l[-1]]:
            create_lines()
    
create_lines()

2. ChatGPT提供的递归函数仅能生成部分目标路径，代码及结果如下：

def all_paths(graph, start, end, path=[]):
    path = path + [start]
    if start == end:
        return [path]
    if not graph.get(start):
        return []
    paths = []
    for node in graph[start]:
        if node not in path:
            new_paths = all_paths(graph, node, end, path)
            for new_path in new_paths:
                paths.append(new_path)
    return paths

# Given dictionary
graph_dict = {1: [2, 6], 2: [3], 6: [5], 3: [4], 5: [8, 9], 4: [5, 7]}

# Define the start and end points
start_point = 1
end_point = 8

# Find all possible paths
paths = all_paths(graph_dict, start_point, end_point)

# Filter paths that do not end with the end point
valid_paths = [p for p in paths if p[-1] == end_point]

# Print the valid paths
print(valid_paths)

运行结果：[[1, 2, 3, 4, 5, 8], [1, 6, 5, 8]]

正确递归实现方案 #

核心思路：用深度优先搜索（DFS）递归遍历每个节点的子节点，当当前节点没有子节点时，当前路径即为有效路径，加入结果集。

代码实现：

def find_all_leaf_paths(graph, start):
    paths = []
    
    def dfs(current_node, current_path):
        # 生成当前路径的副本，避免递归中修改原路径
        current_path = current_path + [current_node]
        # 获取当前节点的子节点，无对应键则返回空列表
        children = graph.get(current_node, [])
        if not children:
            # 无后续节点，将当前路径加入结果
            paths.append(current_path)
            return
        # 递归遍历每个子节点
        for child in children:
            dfs(child, current_path)
    
    dfs(start, [])
    return paths

# 测试示例
graph_dict = {1: [2, 6], 2: [3], 6: [5], 3: [4], 5: [8, 9], 4: [5, 7]}
result = find_all_leaf_paths(graph_dict, 1)
print(result)

运行结果：
[[1, 2, 3, 4, 5, 8], [1, 2, 3, 4, 5, 9], [1, 2, 3, 4, 7], [1, 6, 5, 8], [1, 6, 5, 9]]

方案说明 #

• 每次递归都基于当前路径生成新的副本，避免了原代码中修改共享列表导致的无限循环问题。
• 自动识别所有叶子节点（无后续节点的节点），无需指定固定终点，解决了ChatGPT代码只能生成单一终点路径的局限。

内容的提问来源于stack exchange，提问作者user3301428