如何用Python获取DataFrame中各ID的所有关联关系？

一、需求本质 #

你要实现的是计算有向图中每个节点的所有可达节点（包含直接、间接关联，甚至循环关联），也就是生成关系的传递闭包。从示例来看，因为存在循环（如1↔2），最终同一个连通分量里的所有节点会两两建立关联。

二、数据结构合理性分析 #

是否合理完全取决于你的业务场景：

• 如果业务需要直接查询每个节点能触达的所有关联节点（比如权限继承、实体关联扩散），这种全关联表是合理的，能省去每次查询时的动态计算成本。
• 但必须警惕数据爆炸风险：
  • 若原始数据中的节点构成一个大的强连通分量（所有节点互相可达），最终记录数会是节点数²。比如1000个节点的分量会生成100万条记录，15k行原始数据如果对应大分量，结果数据量会非常庞大，存储和查询成本都会陡增。
  • 如果原始数据是多个独立的小连通分量，数据量增长会相对可控，但仍需评估每个分量的节点规模。

三、树结构是否适用？ #

不适用。树结构是无环的层级结构，但你的数据存在循环关联（如1→2→1），且节点存在多父/多子关联，这更符合有向图的特征，应该用图结构来建模和处理。

四、Pandas处理思路（传递闭包实现） #

可以通过迭代合并的方式计算所有可达关系：

1. 初始化关联表：将原始的Parent-Child关系去重后作为初始表。
2. 迭代扩展关联：
   • 将当前表与自身做连接，把a→b和b→c合并为a→c
   • 将新生成的关联加入总表并去重
   • 重复直到没有新的关联产生
3. 最终得到每个节点的所有可达节点。

示例代码思路（简化版）：

import pandas as pd

# 原始数据
df = pd.DataFrame({
    'Parent': [1,1,2,2,3],
    'Child': [2,3,1,4,2]
})

# 初始化闭包表，去重
closure = df.drop_duplicates().copy()

while True:
    # 连接得到间接关联：Parent -> Child的Child作为新的Parent，关联到原Child的Child
    new_relations = pd.merge(closure, closure, left_on='Child', right_on='Parent', how='inner')
    new_relations = new_relations[['Parent_x', 'Child_y']].rename(columns={'Parent_x':'Parent', 'Child_y':'Child'})
    new_relations = new_relations.drop_duplicates()
    
    # 找出新增的关联
    added = new_relations[~new_relations.isin(closure.to_dict('list')).all(axis=1)]
    
    if added.empty:
        break
    
    # 合并到闭包表
    closure = pd.concat([closure, added]).drop_duplicates()

# 排序后输出
closure = closure.sort_values(['Parent', 'Child']).reset_index(drop=True)
print(closure)

如果存在大量循环或大连通分量，迭代次数会增加，可考虑用networkx等图库优化性能，直接调用图的可达性计算方法。

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