迭代时修改集合的Pythonic设计及图遍历场景技术问询

我最近在做一种图遍历操作，用collections.defaultdict(set)来存储节点的邻接关系——每个键对应节点，值是一个集合，里面存着该节点的所有邻接节点。

遍历过程里的核心逻辑是这样的：针对当前节点curr，找出它的每一对不同的邻接节点e1和e2，然后做两种操作：

• 如果e1和e2之间已经有边，就断开这条连接
• 如果e1和e2之间没有边，就给它们建立连接，同时断开这两个节点和当前节点curr的连接

对应的代码示例（补全了未写完的部分）：

from collections import defaultdict

# 初始化邻接表
edgemap = defaultdict(set)
# 假设已经填充了节点的邻接关系...

curr = 某个当前遍历的节点
# 遍历当前节点的所有邻接节点对
for e1 in edgemap[curr]:
    for e2 in edgemap[curr]:
        if e1 != e2:
            # 检查e1和e2之间是否有边
            if e1 in edgemap[e2]:
                # 断开e1和e2的边（双向都要移除）
                edgemap[e2].remove(e1)
                edgemap[e1].remove(e2)
            else:
                # 给e1和e2建立边
                edgemap[e1].add(e2)
                edgemap[e2].add(e1)
                # 断开e1、e2和当前节点curr的连接
                edgemap[curr].remove(e1)
                edgemap[curr].remove(e2)
                edgemap[e1].remove(curr)
                edgemap[e2].remove(curr)

这里有个实用的优化点：上面的嵌套循环会重复处理同一对节点（比如先处理e1=A,e2=B，再处理e1=B,e2=A），做很多冗余操作。可以用itertools.combinations直接生成所有不重复的节点对，提升效率：

from itertools import combinations

# 先把当前节点的邻接节点转成列表，避免遍历过程中集合变化导致的问题
neighbors = list(edgemap[curr])
for e1, e2 in combinations(neighbors, 2):
    if e1 in edgemap[e2]:
        edgemap[e2].remove(e1)
        edgemap[e1].remove(e2)
    else:
        edgemap[e1].add(e2)
        edgemap[e2].add(e1)
        # 用discard替代remove，避免元素不存在时报错
        edgemap[curr].discard(e1)
        edgemap[curr].discard(e2)
        edgemap[e1].discard(curr)
        edgemap[e2].discard(curr)

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