邻接矩阵在Python中未正确填充

Question

我尝试实现一个简单的邻接矩阵，用于跟踪无向图中哪些节点连接到哪些节点。然而，我的邻接矩阵一直出错，改变整个列而不是单个单元格。以下是我的代码：

def setup_adj_matrix(size, edges):
    # initialize matrix with zeros
    adj_matrix = [[0] * size] * size
    # edges is a list of tuples, representing 2 nodes connected by an edge
    for edge in edges:
        v1 = edge[0]
        v2 = edge[1]
        adj_matrix[v1][v2] = 1
        adj_matrix[v2][v1] = 1
    for row in adj_matrix:
        print row

对于一个有3个节点（0，1，2）和边[(0,1),(0,2),(1,2)]的图形，我应该会得到

[[0,1,1],
 [1,0,1],
 [1,1,0]]

然而，我得到了全部为1的结果。有任何想法问题可能出在哪里？

- JP_smasher

---

http://docs.python.org/2/library/stdtypes.html#sequence-types-str-unicode-list-tuple-bytearray-buffer-xrange - 注意该段落中的两个可能会解决您的问题。 - ersran9

Answer 1

用列表和整数进行乘法运算会返回对同一列表的多个引用，而不是多个副本。你的数组包含了同一个对象九次。

您可以使用双重列表推导来创建正确的数组:

def init_matrix(x, y):
    return [[[0] for i in range(x)] for j in range(y)]

- llb

---

谢谢回复！虽然我认为对于我的目的，[0] 应该只是 0 :) - JP_smasher

Answer 2

列表都是彼此的浅拷贝，所以当你编辑其中一个时，你实际上正在编辑每一行。试试这个来初始化矩阵：

adj_matrix = [[0] * size for i in range(size)]

- thegrinner

Answer 3

其他答案已经很好地回答了你的问题，但是如果你要使用邻接矩阵进行任何重型操作，使用numpy可能更为合适。另外，初始化较为简单且打印数组已内置：

import numpy as np

def setup_adj_matrix(N, edges):
    A = np.zeros((N,N), dtype=int)

    for (v1,v2) in edges:
        A[v1,v2] = A[v2,v1] = 1
    return A

print setup_adj_matrix(3,[(0,1),(0,2),(1,2)])

这会得到：

[[0 1 1]
 [1 0 1]
 [1 1 0]]

- Hooked