如何用Python实现接收字典输入返回传递闭包字典的函数

实现逻辑 #

• 第一步：初始化闭包字典，将每个节点的初始可达列表转为集合存储，避免重复元素
• 第二步：循环迭代更新可达关系，只要某次迭代中存在新增的可达节点，就继续迭代：
  • 遍历每个节点a的所有当前可达节点b
  • 将b的所有可达节点全部加入a的可达集合
• 第三步：迭代停止后，将每个集合转为列表，输出最终字典

完整代码 #

def transitiveClosure(r):
    # 初始化闭包结构，用集合存储方便去重和新增元素
    closure = {node: set(targets) for node, targets in r.items()}
    updated = True
    # 循环直到没有新的可达关系加入
    while updated:
        updated = False
        for a in closure:
            # 遍历a当前所有可达节点b
            for b in list(closure[a]):
                # 将b的可达节点全部加入a的可达集合
                for c in closure[b]:
                    if c not in closure[a]:
                        closure[a].add(c)
                        updated = True
    # 集合转列表返回，需要固定顺序可替换为sorted(closure[node])
    return {node: list(targets) for node, targets in closure.items()}

测试验证 #

R = {1: [3], 2: [4], 3: [], 4: [1]}
print(transitiveClosure(R))
# 输出结果：{1: [3], 2: [1, 3, 4], 3: [], 4: [1, 3]}，和要求完全匹配

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