需要从python lis中找到子元素

Question

我有一个python列表如下

[(u'1', u'0'), (u'2', u'1'), (u'3', u'2'), (u'4', u'3'), (u'5', u'4'), (u'6', u'4'), (u'7', u'4'), (u'8', u'4'), (u'9', u'4'), (u'10', u'4'), (u'11', u'4'), (u'11.5', u'2'), (u'12', u'11.5'), (u'13', u'11.5'), (u'14', u'11.5'), (u'15', u'11.5'), (u'16', u'11.5'), (u'17', u'11.5'), (u'18', u'11.5'), (u'19', u'11.5'), (u'20', u'11.5'), (u'21', u'11.5'), (u'22', u'11.5'), (u'23', u'11.5'), (u'24', u'11.5'), (u'25', u'11.5'), (u'26', u'11.5'), (u'27', u'11.5'), (u'28', u'11.5'), (u'30', u'11.5'), (u'29', u'11.5')]

这里每个元组的第一位是它自己的id，第二位是它的父id

我要得到所有有特定身份的孩子。 例如，如果我想得到所有属于child（或child的child）的ownID的列表。。。至n深度）的自身id“3”。 所以答案列表是[u'4', u'5', u'6', u'7', u'8', u'9', u'10', u'11']

有什么办法吗？？在

Answer 1

您可以使用networkx库。。。在

import networkx as nx
g = nx.DiGraph()
g.add_edges_from( (y,x) for x,y in your_list )
print list(nx.dfs_postorder_nodes(g, '3'))
[u'11', u'10', u'5', u'7', u'6', u'9', u'8', u'4', '3']

Answer 2

如果关系不经常改变，一种解决方案是构建传递闭包，因此：

def tclose(data):
    data = set(data)
    while True:
        new = set( (a, d)
                   for (a, b) in data
                   for (c, d) in data
                   if b == c ) - data
        if not new:
            return data
        data.update(new)

data = tclose([(u'1', u'0'), …])

然后可以定位子体，从而：

^{pr2}$

如果要将搜索限制在固定深度，可以将while True替换为for _ in range(n - 1)。如果n发生变化，则需要不同的解决方案。在

请注意，此解决方案注重简单性。这不是最快的算法，如果你给它一个大的输入集，可能需要进行修复。在

Answer 3

如果您没有定义级别的数目

与您的列表li：

d = {}
for o, p in li:
    d.setdefault(p, []).append(o)
todo = d[u'3'][:]
descendants = []
while todo:
    node = todo.pop(0)
    todo.extend(d.get(node, []))
    descendants.append(node)

descendants包含查找的列表。在