如何根据最小生成树移除无向图邻接表中的对称等价连接？

当然可以实现这个需求，核心思路是：因为无向图的每条边在邻接表里是双向存储的，所以MST中的每条边(s, d, c)对应邻接表中s节点下的(d, c)和d节点下的(s, c)两个条目，我们只需要把这些条目逐个移除即可。

具体实现代码 #

首先定义原始的邻接表和MST集合：

# 邻接表：键为源节点，值是(目标节点, 权重)的集合
adjacency_list: dict[int, set[tuple[int, int]]] = {
    1: {(2, 5), (3, 11), (4, 7)},
    2: {(1, 5), (3, 1)},
    3: {(1, 11), (2, 1), (4, 11)},
    4: {(1, 7), (3, 11)},
}

# 最小生成树：元素为(源节点, 目标节点, 权重)的元组集合
mst: set[tuple[int, int, int]] = {
    (1, 2, 5),
    (1, 4, 7),
    (2, 3, 1),
}

然后执行移除操作：

# 遍历MST中的每条边，移除邻接表里对应的双向条目
for src, dest, cost in mst:
    # 使用discard避免元素不存在时抛出异常
    adjacency_list[src].discard((dest, cost))
    adjacency_list[dest].discard((src, cost))

# 输出处理后的邻接表
for node, edges in adjacency_list.items():
    print(f"节点 {node}: {edges}")

执行结果 #

运行后会得到处理后的邻接表：

节点 1: {(3, 11)}
节点 2: set()
节点 3: {(1, 11), (4, 11)}
节点 4: {(3, 11)}

这里用discard而不是remove的原因是，discard在要移除的元素不存在时不会报错，容错性更强。

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