从子父关系生成字典树时如何避免循环问题？

我尝试通过子父关系列表生成字典树，但存在子节点包含祖先节点从而产生循环的问题。现有代码如下：

list_child_parent = [(2,1),(3,2),(4,2),(5,3),(6,4),(2,6)]
def make_map(list_child_parent):
    has_parent = set()
    all_items = {}
    for child, parent in list_child_parent:
        if parent not in all_items:
            all_items[parent] = {}
        if child not in all_items:
            all_items[child] = {}
        
        if parent not in all_items[child]:
            all_items[parent][child] = all_items[child]
            has_parent.add(child)
        else:
            continue

    result = {}
    for key, value in all_items.items():
        if key not in has_parent:
            result[key] = value
    return result
make_map(list_child_parent)

该代码仅能处理子节点直接包含父节点的情况，无法处理子节点包含祖父等更远祖先的场景。当前运行结果为：
{1: {2: {3: {5: {}}, 4: {6: {2: {...}}}}}}

期望得到合理的无循环字典树结果，例如：

• {1: {2: {3: {5: {}}, 4: {6: {}}}}}
• {1: {2: {3: {5: {}}, 4: {6: 2}}}}}
• {1: {2: {3: {5: {}}, 4: {6: {2:{}}}}}}}

核心解决思路：构建树前先检测循环路径 #

要避免循环，关键在于在添加子节点到父节点之前，检查该子节点是否已经是当前父节点的祖先节点。以下是具体实现方案：

1. 实现代码（支持两种无循环结果） #

list_child_parent = [(2,1),(3,2),(4,2),(5,3),(6,4),(2,6)]

def get_ancestors(node, parent_map):
    """获取节点的所有祖先节点集合"""
    ancestors = set()
    current = node
    while current in parent_map:
        current = parent_map[current]
        ancestors.add(current)
        # 极端情况防死循环
        if len(ancestors) > len(parent_map):
            break
    return ancestors

def make_tree(list_child_parent, handle_cycle="skip"):
    # 先构建子→父的映射表，方便快速查祖先
    parent_map = {}
    for child, parent in list_child_parent:
        parent_map[child] = parent
    
    # 初始化所有节点的空字典
    all_nodes = set(parent_map.keys()).union(set(parent_map.values()))
    nodes = {node: {} for node in all_nodes}
    has_parent = set()
    
    for child, parent in list_child_parent:
        # 检查子节点是否是父节点的祖先，判断是否存在循环
        if child in get_ancestors(parent, parent_map):
            if handle_cycle == "record_id":
                # 循环时记录节点ID而非引用
                nodes[parent][child] = child
            elif handle_cycle == "skip":
                # 循环时跳过该关系
                continue
        
        # 无循环则正常添加子节点引用
        nodes[parent][child] = nodes[child]
        has_parent.add(child)
    
    # 筛选根节点（没有父节点的节点）
    root_nodes = [node for node in nodes if node not in parent_map]
    return {node: nodes[node] for node in root_nodes}

# 生成第一种预期结果（跳过循环关系）
print(make_tree(list_child_parent, handle_cycle="skip"))
# 生成第二种预期结果（循环时记录节点ID）
print(make_tree(list_child_parent, handle_cycle="record_id"))

代码说明 #

• get_ancestors函数：通过循环遍历父映射表，获取某个节点的所有祖先，用于提前检测循环。
• handle_cycle参数：控制循环的处理方式：
  • "skip"：跳过会产生循环的子父关系，得到{1: {2: {3: {5: {}}, 4: {6: {}}}}}
  • "record_id"：遇到循环时，将子节点以ID形式记录而非引用，得到{1: {2: {3: {5: {}}, 4: {6: 2}}}}}
• 最终生成的字典树完全避免了循环引用，符合预期需求。

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