3

我试图实现一个简单的邻接矩阵来跟踪哪些节点连接到无向图中的哪些节点。但是，我的邻接矩阵不断通过更改整个列而不是单个单元格来搞砸。这是我的代码：

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。问题可能出在哪里？

4

3 回答 3

6

带有列表和 int 的乘法运算符返回对同一个列表的多个引用，而不是多个副本。您的数组包含九次相同的对象。

您可以使用双列表理解创建正确的数组：

def init_matrix(x, y):
    return [[[0] for i in range(x)] for j in range(y)]
于 2013-07-09T15:57:08.357 回答
4

这些列表都是彼此的浅表副本，因此当您编辑一个列表时，您实际上是在编辑每一行。试试这个来初始化矩阵：

adj_matrix = [[0] * size for i in range(size)]
于 2013-07-09T15:56:46.817 回答
2

其他答案在解决您的问题方面做得很好，但是如果您要对邻接矩阵进行任何繁重的工作，那么使用 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]]
于 2013-07-09T16:12:42.287 回答