在python中查找顶级父级的所有子级

Question

我有一个父-子关系的列表，其中的结构不是一个真正的树。有些父母可以有许多子女，也有些子女可以有一个以上的父母。在

import pandas as pd    
df = pd.DataFrame([[123,234],[123,235],[123,236],[124,236],[234,345],[236,346]], columns=['Parent','Child'])*

我想把所有的孩子归为特定的祖先。根据数据：

^{pr2}$

应该是正确的组。在

我试过：

parents = set()
children = {}
for p, c in df.to_records(index=False).tolist():
    parents.add(p)
    children[c] = p


def getAncestors(p):
    return (getAncestors(children[p]) if p in children else []) + [p]

但在346，它只返回一个组。在

另外，如何找到123和124的所有子代？在

谢谢你！在

Answer 1

正如您所说，它不是真正的树，而是更像一个有向无环图，因此您不能将每个子节点映射到一个父节点；它必须是一个父节点的列表。另外，考虑到您的用例，我建议将父母映射到他们的子列表。在

relations = [[123,234],[234,345],[123,235],[123,236],[124,236],[236,346]]

children = {}
for p, c in relations:
    children.setdefault(p, []).append(c)
roots = set(children) - set(c for cc in children.values() for c in cc)

然后，您可以使用一个递归函数，该函数类似于将所有子节点获取到给定根节点（或任何父节点）的递归函数。根本身不在列表中，但可以很容易地添加。在

^{pr2}$