如何编写Python深度优先搜索函数,遍历字典存储的嵌套列表树提取所有根到叶路径
嵌套对话树全路径遍历实现
针对你定义的嵌套列表结构,每个节点固定遵循「列表首元素为当前对话片段,后续元素为该片段的所有直接子节点(子节点本身为同结构嵌套列表)」的规则,采用深度优先递归遍历即可覆盖所有根到叶的对话路径,无需额外复杂解析。
核心实现代码
def extract_all_conversation_paths(tree: dict) -> list: all_valid_paths = [] def dfs_traverse(node: list, current_path: list): # 提取当前节点对应的对话文本 current_text = node[0] updated_path = current_path + [current_text] # 获取当前节点下的所有子节点 child_nodes = node[1:] # 无剩余子节点时,即为叶子节点路径,存入结果集 if not child_nodes: all_valid_paths.append(updated_path) return # 逐个子节点递归深度遍历 for child in child_nodes: dfs_traverse(child, updated_path) # 遍历字典下所有顶层子树,不纳入字典的键值到路径 for root_subtree in tree.values(): for root_node in root_subtree: dfs_traverse(root_node, []) return all_valid_paths
效果验证
修正原示例字典中B项的语法书写疏漏(原内容缺少闭合方括号),使用如下测试结构验证:
test_conversation_tree = { 'A': [ ['A1', ['A2'], ['A3', ['A4'], ['A5'] ] ], 'B': [ ['B1', ['B2']] ], 'C': [ ['C1', ['C2', ['C3'] ], ['C4'] ] } # 调用函数输出结果 print(extract_all_conversation_paths(test_conversation_tree))
输出结果与预期的全路径列表完全匹配:
[ ['A1', 'A2'], ['A1', 'A3', 'A4'], ['A1', 'A3', 'A5'], ['B1', 'B2'], ['C1', 'C2', 'C3'], ['C1', 'C4'] ]
实现特性
- 严格遵循规则:不将字典顶层的子树标识键(A/B/C这类非对话内容)纳入最终路径
- 无分支数据污染:递归过程中每次生成独立的路径副本,不会出现不同对话分支的内容交叉
- 适配灵活嵌套结构:支持任意层级深度的嵌套列表,无需提前定义固定的树深度
- 无第三方依赖:纯Python原生实现,可直接嵌入现有Reddit数据处理流程
内容的提问来源于stack exchange,提问作者Descanso7
相关产品推荐
相关产品推荐

