由于某种原因在列表中设置自联合

Question

我正在尝试用 Python 编写最小权重树的 Kruskal 算法，其中加权边表示为元组列表 ({i,j},w)，其中 {i,j} 是边，w是重量。但经过 if （验证其连接）后，第一条边变成了节点集。 我放置了一些打印件来发现它在哪里发生了变化，这是我尝试过的：

import itertools
import random

def conexo(X,A):
  #X : set of nodes
  #A : list of edges {i,j}
  if set().union(*A)!=X: #if there are isolated nodes
    return False
  else:
    G={i:set().union(*[a for a in A if i in a])-{i} for i in X} #{node: successors set}
    C=A[0] #connected nodes
    for i in G: #eliminate C from the successors set
      G[i]-=C

    while True:
      suc=list(set().union(*[G[i] for i in C])) #successors list
      if suc==list(): break #if there are no more successors, the loop finishes
      j=suc[0] #chooses a successor
      C|={j} #adds j to the set of connected nodes
      for i in G: #takes off j from the successors sets
          G[i]-={j}
    if C==X: #if al nodes are connected
      return True
    else:
      return False

def kruskal(X,G):
  #X : set of nodes
  #G : list of weighted edges ({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): #THE BREAKING POINT OF THE PROBLEM
    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)]

Answer 1

Python 是按引用传递的，这意味着变量赋值和函数参数不会创建对象的副本，因此对对象的任何修改都会反映在外部。在您的情况下，这是通过

A

发生的，您可以将

A[0]

分配给

C

，然后在

C|={j}

行中进行修改。

例如，可以通过在将其分配给

A[0]

时显式创建

C

的副本来修复此问题：

    # ...
    G={i:set().union(*[a for a in A if i in a])-{i} for i in X} #{node: successors set}
    C=set(A[0]) #connected nodes
    for i in G: #eliminate C from the successors set
      G[i]-=C
    # ...