基于子父元组列表遍历树收集指定节点后代，求该问题的标准名称

你描述的场景涉及的标准专业术语如下：

• 你使用的(child, parent)元组构成的列表，是树/图的标准存储结构之一，标准命名为边列表（Edge List），针对树结构的场景也常称为父子边集。
• 你要实现的「收集指定节点所有后代」的操作，标准命名为后代查询（Descendant Query），是树结构的基础查询操作之一。
• 针对边列表存储的树，实现后代查询的通用方案是从目标节点出发，做广度优先搜索（BFS） 或 深度优先搜索（DFS） 遍历，收集所有可达的子节点即可，这两种是图/树遍历的标准算法。
• 如果需要高频执行后代查询，业界常见的优化方案是对树做预编码，常用的有两类：
  • 嵌套集模型（Nested Set Model，也叫左右值编码模型）
  • 路径枚举模型（Path Enumeration，也叫物化路径模型）
    这两种方案可以把后代查询的复杂度从遍历的O(n)降低到接近O(k)（k为后代节点数量），适合树结构变更频率低、查询需求多的场景。

示例实现（基于BFS） #

针对你给出的示例，用Python实现的BFS版本后代查询代码如下：

in_list = [(2,1),(3,2),(4,3),(6,5),(7,4),(8,4)]
# 先把边列表转换为「父节点-子节点列表」的邻接映射
parent_to_children = {}
for child, parent in in_list:
    parent_to_children.setdefault(parent, []).append(child)

def get_descendants(target_node, adj_map):
    descendants = []
    # 初始化队列，放入目标节点的直接子节点
    queue = adj_map.get(target_node, [])
    while queue:
        current = queue.pop(0)
        descendants.append(current)
        # 把当前节点的子节点加入队列继续遍历
        queue.extend(adj_map.get(current, []))
    return descendants

print(get_descendants(2, parent_to_children)) # 输出 [3, 4, 7, 8]

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