如何基于Pandas DataFrame生成完整的父子层级递归路径？

问题场景 #

现有如下父子关系的数据集：

需要生成所有可能的层级路径，预期输出：

A|B
A|C
A|B|D
A|B|C
A|C|D
A|B|C|D

但用networkx实现时，只得到了A|B|D和A|B|C|D，漏掉了A|B、A|B|C、A|C这类中间路径。

解决方法 #

不用依赖networkx，直接用递归遍历+收集中间路径的方式就能搞定，步骤如下：

1. 构建父子映射字典 #

先把DataFrame转成父节点到子节点的映射，方便后续递归查找：

import pandas as pd

# 加载数据
df = pd.DataFrame({
    'Parent': ['A', 'A', 'B', 'B', 'C'],
    'Child': ['B', 'C', 'D', 'C', 'D']
})

# 生成父->子的映射字典
parent_child_map = df.groupby('Parent')['Child'].apply(list).to_dict()

2. 递归遍历收集所有路径 #

写个递归函数，每遍历到一个节点，只要当前路径长度≥2（即包含至少一个父子对），就把路径加入结果，然后继续遍历子节点：

def collect_all_paths(start, current_path, result):
    # 只要路径有至少两个节点，就加入结果
    if len(current_path) >= 2:
        result.append('|'.join(current_path))
    # 遍历当前节点的所有子节点，继续递归
    for child in parent_child_map.get(start, []):
        collect_all_paths(child, current_path + [child], result)

# 初始化结果，从根节点A开始遍历
all_paths = []
collect_all_paths('A', ['A'], all_paths)

# 输出结果
for path in all_paths:
    print(path)

运行效果 #

执行后会输出：

A|B
A|B|D
A|B|C
A|B|C|D
A|C
A|C|D

如果需要和预期顺序完全一致，加个排序即可：

for path in sorted(all_paths):
    print(path)

问题原因分析 #

之前用networkx的代码大概率只收集了到叶子节点的完整路径，没有把那些还能继续延伸的中间路径（比如A|B这种，B还有子节点，但本身也是一个有效路径）纳入结果。上面的方法在每一步递归时都会检查并保存中间路径，所以能覆盖所有预期结果。

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