Python中删除图结构指定节点并重排节点编号

需求描述 #

• 输入为节点映射字典nodes：键是节点坐标元组，值是对应节点编号
• 需要移除坐标存在于列表T中的所有节点
• 剩余节点保留原有排序逻辑，重新分配从1开始的连续编号，生成新的节点字典

测试样例 #

输入 #

nodes={(0, 0): 1,
 (0, 1): 2,
 (0, 2): 3,
 (1, 0): 4,
 (1, 1): 5,
 (1, 2): 6,
 (2, 0): 7,
 (2, 1): 8,
 (2, 2): 9}

T=[(2, 0),(2,1)]

期望输出 #

newnodes={(0, 0): 1,
 (0, 1): 2,
 (0, 2): 3,
 (1, 0): 4,
 (1, 1): 5,
 (1, 2): 6,
 (2, 2): 7}

实现代码 #

# 待移除坐标转集合，优化成员查询效率
to_remove = set(T)
# 按原有节点编号升序排列，过滤掉需要移除的节点
remaining = [
    coord for coord, _ 
    in sorted(nodes.items(), key=lambda item: item[1])
    if coord not in to_remove
]
# 按顺序分配从1开始的连续编号，生成新字典
newnodes = {coord: idx for idx, coord in enumerate(remaining, start=1)}

逻辑说明 #

• 排序时显式指定按原节点编号排序，兼容所有Python版本的字典遍历规则，不会出现顺序错乱
• 待移除坐标转为集合后，判断坐标是否需要删除的操作时间复杂度为O(1)，节点规模较大时性能优势明显
• 借助enumerate的start参数直接生成从1开始的连续编号，代码简洁无冗余

运行上述代码后得到的newnodes和期望输出完全一致。

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