如何使用pandas查找层级结构中子节点到父节点的全量关联路径

核心思路 #

• 先识别所有终极父节点：即出现在Parent列、但从未出现在Child列的节点，这类节点没有上层父节点，是所有路径的终点
• 为所有节点构建邻接关系表，同时存储每条父子边对应的Class属性
• 对每个初始子节点执行深度优先遍历，记录完整路径、继承的起始Class，遍历到终极父节点时输出一条完整关联记录
• 最后根据路径长度判断关联类型：路径仅包含2个节点为Direct，否则为Indirect

完整可运行代码 #

import pandas as pd

# 输入数据
df = pd.DataFrame({
    'Child': ['1', '1', '1', '1', '2', '2', '2', '3', '4', '5'], 
    'Parent': ['2','3','4','9','4','6','8','6','5','6'],
    'Class': ['C','C','B','A','B','D','S','C','A','D']
})

# 1. 构建邻接表和终极父节点集合
adj = {}
edge_class = {}
all_child = set(df['Child'].unique())
all_parent = set(df['Parent'].unique())
ultimate_parents = all_parent - all_child  # 终极父节点：没有子节点的父节点

for _, row in df.iterrows():
    child, parent, cls = row['Child'], row['Parent'], row['Class']
    if child not in adj:
        adj[child] = []
    adj[child].append(parent)
    edge_class[(child, parent)] = cls

# 2. DFS遍历所有路径
result = []
def dfs(current_node, start_cls, path):
    # 如果当前节点是终极父节点，保存结果
    if current_node in ultimate_parents:
        result.append({
            'Child': path[0],
            'Ultimate_Parent': current_node,
            'Class': start_cls,
            'Path': '-'.join(path),
            'Connection': 'Direct' if len(path) == 2 else 'Indirect'
        })
        return
    # 否则继续遍历下一层父节点
    for next_parent in adj.get(current_node, []):
        dfs(next_parent, start_cls, path + [next_parent])

# 3. 对每个初始子节点启动遍历
for _, row in df.iterrows():
    start_child = row['Child']
    start_cls = row['Class']
    first_parent = row['Parent']
    dfs(first_parent, start_cls, [start_child, first_parent])

# 4. 转换为DataFrame输出
output_df = pd.DataFrame(result)
print(output_df.sort_values(by=['Child', 'Class']).reset_index(drop=True))

输出验证 #

运行上述代码得到的结果和你给出的期望输出完全一致，包含所有可能的关联路径，不会遗漏多路径场景。

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