遍历树收集所有子节点，不包括不相关的分支

Question

我有一个子-父元组列表。我想遍历树以收集输入节点的所有子节点。

in_list = [(2,1),(3,2),(4,3),(6,5),(7,4),(8,4)]

现在假设我想收集节点 2 的所有子节点。那将是

out_list = [3,4,7,8]

这个问题或者它的解决方案有什么具体的名称吗？只需要知道去哪里找。

Answer 1

你需要像DFS一样遍历in_list中的这些节点，你可以试试这个：

def DFS(path, lst, father):
    for (a,b) in lst:
        if b == father:
            path.append(a)
            DFS(path, lst, a)
    return path

in_list = [(2,1),(3,2),(4,3),(6,5),(7,4),(8,4)]
res = DFS([], in_list , 2)
print(res)

输出：

[3, 4, 7, 8]

Answer 2

您可以使用递归生成器函数：

in_list = [(2,1),(3,2),(4,3),(6,5),(7,4),(8,4)]
def paths(n, c = []):
   if not (t:=[a for a, b in in_list if b == n]):
      yield from (c + [n])
   else:
      yield from [j for k in t for j in paths(k, c+[n])]

print([*set(paths(2))][1:])

输出：

[3, 4, 7, 8]

遍历树收集所有子节点，不包括不相关的分支

Traverse tree to collect all children nodes, excluding unrelated branches

python

algorithm

tree

traversal