基于Python的有向树全路径枚举代码问题求助

现有代码问题排查 #

你写的迭代逻辑存在几个核心错误：

• 漏掉了无后继节点作为起点的场景（比如示例中的节点2、4，单独成路径的情况无法被捕获）
• 多分支遍历逻辑错误，比如节点1同时有后继2和3，现有嵌套循环只能遍历其中一条分支，无法覆盖所有路径
• 节点取值错误：current_node = j 行取的是邻接表的下标而非实际存储的后继节点值
• path的拼接和重置时机错误，会出现路径冗余或者丢失的问题

正确递归实现方案 #

我们采用深度优先遍历实现，每个节点作为起点单独启动递归，遍历到死端时直接保存路径即可：

# 示例邻接表
adj = [[1,2],[2,3],[],[4],[]]
full_path = []

def dfs(current_node, current_path):
    # 拷贝路径避免递归过程中互相干扰
    new_path = current_path.copy()
    new_path.append(current_node)
    # 到达死端，保存路径
    if not adj[current_node]:
        full_path.append(new_path)
        return
    # 遍历所有后继节点递归
    for next_node in adj[current_node]:
        dfs(next_node, new_path)

# 遍历所有节点作为路径起点
for start_node in range(len(adj)):
    dfs(start_node, [])

print(full_path)

输出验证 #

运行上述代码输出结果为：
[[0,1,2], [0,1,3,4], [0,2], [1,2], [1,3,4], [2], [3,4], [4]]
完全符合要求的标准输出。

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