如何构建值包含关联键对应值的Python字典？

问题描述 #

给定一个字典，其中每个键对应一个集合。当集合中的元素是字典的其他键时，需要将该元素对应的集合所有元素添加到当前键的集合中，重复此操作直到无新元素可添加。示例如下：

d1 = {1: {2}, 2: {3}}
d2 = {1: {2, 3}, 2: {3}}

d3 = {1: {10, 20, 30}, 10: {11}, 20: {21}, 30: {31}}
d4 = {1: {10, 11, 20, 21, 30, 31}, 10: {11}, 20: {21}, 30: {31}}

d5 = {1: {2}, 2: {3}, 3: {4}}
d6 = {1: {2, 3, 4}, 2: {3, 4}, 3: {4}}

实现代码 #

以下是Python实现，通过循环迭代直到没有新元素添加，本质是对每个节点的可达集合进行广度优先扩展：

def expand_dict_closure(input_dict):
    # 复制原字典，避免修改原始数据
    expanded = {key: set(values) for key, values in input_dict.items()}
    updated = True
    
    while updated:
        updated = False
        # 遍历每个键的当前集合
        for key in list(expanded.keys()):
            current_elements = expanded[key].copy()
            for elem in current_elements:
                # 如果元素是字典的键，且存在未添加的新元素
                if elem in expanded:
                    new_items = expanded[elem] - expanded[key]
                    if new_items:
                        expanded[key].update(new_items)
                        updated = True
    return expanded

# 测试示例
d1 = {1: {2}, 2: {3}}
print(expand_dict_closure(d1))  # {1: {2, 3}, 2: {3}}

d3 = {1: {10, 20, 30}, 10: {11}, 20: {21}, 30: {31}}
print(expand_dict_closure(d3))  # {1: {10, 11, 20, 21, 30, 31}, 10: {11}, 20: {21}, 30: {31}}

d5 = {1: {2}, 2: {3}, 3: {4}}
print(expand_dict_closure(d5))  # {1: {2, 3, 4}, 2: {3, 4}, 3: {4}}

更优数据结构与相关思路 #

这个问题本质是有向图的传递闭包计算：字典的键是图的节点，键对应的集合元素是节点间的有向边，我们需要找出每个节点的所有可达节点。

适合的数据结构与算法 #

1. 优化邻接表：原字典本身就是邻接表的一种形式，但如果需要频繁更新或查询，可以用更高效的集合存储（比如Python的set已经很适合），配合BFS/DFS遍历计算可达性。
2. 传递闭包矩阵：如果节点是连续整数且数量较少，可以用布尔矩阵表示节点间的可达关系，通过Floyd-Warshall算法一次性计算所有节点的传递闭包，时间复杂度O(n³)，适合小图场景。
3. 拓扑排序+动态规划：如果图是有向无环图（DAG），可以先对节点拓扑排序，再按顺序计算每个节点的可达集合，时间复杂度可降至O(V+E)，比通用BFS更高效。

相关关键词 #

传递闭包、有向图、邻接表、Floyd-Warshall算法、拓扑排序、BFS/DFS遍历

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