Python实现Kruskal算法时集合意外合并问题求助

问题描述 #

我在Python中实现最小生成树的Kruskal算法，带权边以元组({i,j},w)的列表形式表示，其中{i,j}为边的节点集合，w为权重。但执行连通性验证的if语句后，第一个边的集合变成了全节点集合，通过打印语句定位到问题出在连通性检查的conexo函数调用后。

相关代码 #

import itertools
import random

def conexo(X,A):
  #X : 节点集合
  #A : 边的集合列表 {i,j}
  if set().union(*A)!=X: # 存在孤立节点
    return False
  else:
    G={i:set().union(*[a for a in A if i in a])-{i} for i in X} #{节点: 邻接节点集合}
    C=A[0] # 初始连通节点集合
    for i in G: # 从邻接集合中移除已连通节点
      G[i]-=C

    while True:
      suc=list(set().union(*[G[i] for i in C])) # 所有连通节点的邻接节点
      if suc==list(): break # 没有新节点可连通时退出循环
      j=suc[0] # 选取一个邻接节点
      C|={j} # 将节点加入连通集合
      for i in G: # 从所有邻接集合中移除该节点
          G[i]-={j}
    if C==X: # 所有节点都连通
      return True
    else:
      return False

def kruskal(X,G):
  #X : 节点集合
  #G : 带权边列表 ({i,j},p)
  print('G',G)
  G.sort(key=lambda tup : tup[1])
  print('G',G)
  A=[g[0] for g in G]
  if conexo(X,A): # 问题触发点
    print('G',G)
    tree=[G[0]]
    aris=[G[0][0]]
    for i in range(1,len(G)):
      if not conciclo(aris+[G[i][0]]):
        tree.append(G[i])
        aris.append(G[i][0])
      if len(tree)==len(X)-1:
        break
    return tree
  else:
    return 'disconex'

测试输入 #

X={i for i in range(1,5)}
g=[({1,2},1),({1,3},1),({2,4},1),({2,3},5)]
print(kruskal(X,g))

预期输出 #

G [({1, 2}, 1), ({1, 3}, 1), ({2, 4}, 1), ({2, 3}, 5)]
G [({1, 2}, 1), ({1, 3}, 1), ({2, 4}, 1), ({2, 3}, 5)]
G [({1, 2}, 1), ({1, 3}, 1), ({2, 4}, 1), ({2, 3}, 5)]
[({1, 2}, 1), ({1, 3}, 1), ({2, 4}, 1)]

实际输出 #

G [({1, 2}, 1), ({1, 3}, 1), ({2, 4}, 1), ({2, 3}, 5)]
G [({1, 2}, 1), ({1, 3}, 1), ({2, 4}, 1), ({2, 3}, 5)]
G [({1, 2, 3, 4}, 1), ({1, 3}, 1), ({2, 4}, 1), ({2, 3}, 5)]
[({1, 2, 3, 4}, 1), ({1, 3}, 1), ({2, 4}, 1)]

问题原因 #

Python中集合是可变对象，当执行A = [g[0] for g in G]时，A中的每个元素都是直接引用G里对应元组中的集合，而非创建副本。在conexo函数中，C = A[0]让C指向了G[0][0]的集合对象，后续执行C |= {j}时，直接修改了这个原集合，导致G中的第一个边集合被意外扩容为全节点集合。

解决方案 #

修改conexo函数中初始化C的代码，创建原集合的副本，避免修改原对象：

# 将原代码中的
C = A[0]
# 修改为
C = set(A[0])

修改后，C是一个新的集合对象，后续对C的修改不会影响G中的原边集合，运行代码即可得到预期输出。

内容的提问来源于stack exchange，提问作者Wei Le Hu Tang