影響其他對象列表的對象列表

Question

我試圖建立一個圖形，其中一個頂點有一個字符串標識符，並連接到另一個頂點，如果兩個頂點的字符串標識符只相差一個字符。例如，'狗'和'點'可以通過邊緣連接。我使用鄰接列表維護圖。但是，在驗證了可以連接2個頂點之後，我將to_vertex對象附加到from_vertex對象的列表中，反之亦然。但是這導致列表包含重複的對象。以下是代碼（這是相當密集）：

class vertex(): 
    def __init__(self, distance = -1, edges = [], name = ''): 
     self.name = name 
     self.distance = distance 
     self.edges = edges 

def create_graph(word_dict): 
    graph = [] 

    num_words = len(word_dict) 

    v = [vertex(name = word_dict[x]) for x in range(num_words)] 

    for i in range(num_words): 
     for j in range(i + 1, num_words): 
      count = 0 
      if len(word_dict[i]) == len(word_dict[j]): 
       print word_dict[i], word_dict[j] 
       k = 0 
       is_valid = True 
       while k < len(word_dict[i]): 
        print word_dict[i][k], word_dict[j][k] 
        if word_dict[i][k] != word_dict[j][k]: 
         if count == 1: 
          is_valid = False 
          break 
         else: 
          count += 1 
          k += 1 
        else: 
         k += 1 

       if is_valid == True: 
        v[i].edges.append(v[j]) 
        v[j].edges.append(v[i]) 

    graph = [v[i] for i in range(num_words)] 

    return graph 

if __name__ == '__main__': 
    graph = create_graph(['bat', 'cot', 'dog', 'dag', 'dot', 'cat']) 

    for v in graph: 
     print 'Vertex name ' + v.name 
     for edge in v.edges: 
      print edge.name 
     print '-----------------------------' 

以下是的輸出爲環路主：

Vertex name bat 
cat 
bat 
dot 
cot 
cat 
cot 
dag 
dog 
dot 
dog 
----------------------------- 
Vertex name cot 
cat 
bat 
dot 
cot 
cat 
cot 
dag 
dog 
dot 
dog 
----------------------------- 
Vertex name dog 
cat 
bat 
dot 
cot 
cat 
cot 
dag 
dog 
dot 
dog 
----------------------------- 
Vertex name dag 
cat 
bat 
dot 
cot 
cat 
cot 
dag 
dog 
dot 
dog 
----------------------------- 
Vertex name dot 
cat 
bat 
dot 
cot 
cat 
cot 
dag 
dog 
dot 
dog 
----------------------------- 
Vertex name cat 
cat 
bat 
dot 
cot 
cat 
cot 
dag 
dog 
dot 
dog 
----------------------------- 

通過一些調試，我發現

if is_valid == True: 
    v[i].edges.append(v[j]) 
    v[j].edges.append(v[i]) 

正在造成這個問題，但我只是無法圍繞它來包裹我的頭。這不像我修改第一個append語句中的to_vertex的edges字段，但第一個append語句也影響它。

Answer 1

我不完全確定，但我認爲問題是使用默認值[]爲edges哪（我認爲）創建一個唯一的對象[]，然後默認初始化爲該唯一對象。所以你所有的邊緣將基本上是相同的對象，當你追加到其中一個對象時，你也可以追加到其他對象上。那有意義嗎？

爲避免此問題，請不要使用默認的init，而是強制self.edges = []。

或者，如果你真的希望能夠初始化任意邊緣，你可以試試：

def __init__(self, distance = -1, edges = None, name = ''): 
    self.name = name 
    self.distance = distance 
    if edges is None: 
     edges = [] 
    self.edges = edges 

（讓我知道是否可行，因爲我不知道這個...）