帮同学写一个邻接表转邻接矩阵的程序,程序读入一个邻接表,节点编号从 1 至 1673,要求转成 1673 * 1673 的邻接表。代码如下:
1 | # 邻接矩阵 |
运行后,程序所输出的邻接矩阵元素全为 1,不解。
找原因
单步调试发现,在读邻接表第一行后,有一列被置为了全 1。于是想到 Python 中通过乘法复制元素,在 Python 虚拟机层面只会复制对象的引用。
做个实验:
1 | In [9]: m = [[0] * 10] * 10 |
那么问题来了,对列表应用乘法,为什么 m[0][0] = 1
不会导致整个 m
中的元素变成 1 ?继续尝试:
1 | In [13]: m = [0] * 10 |
很明显,[0] * 10
创建了一个长度为 10 的、元素全为 0 的列表,每个元素都是独立的。验证一下:
1 | In [18]: m[0] is m[1] |
翻阅 Python 文档 3.1. 对象、值与类型,有一段关于可变与不可变类型的描述:
有些对象的 值 可以改变。值可以改变的对象被称为 可变的;值不可以改变的对象就被称为 不可变的。(一个不可变容器对象如果包含对可变对象的引用,当后者的值改变时,前者的值也会改变;但是该容器仍属于不可变对象,因为它所包含的对象集是不会改变的。因此,不可变并不严格等同于值不能改变,实际含义要更微妙。)
一个对象的可变性是由其类型决定的;例如,数字、字符串和元组是不可变的,而字典和列表是可变的。
创建对象时:
类型会影响对象行为的几乎所有方面。甚至对象编号的重要性也在某种程度上受到影响: 对于不可变类型,会得出新值的运算实际上会返回对相同类型和取值的任一现有对象的引用,而对于可变类型来说这是不允许的。例如在
a = 1; b = 1
之后,a
和b
可能会也可能不会指向同一个值为1的对象,这取决于具体实现,但是在c = []; d = []
之后,c
和d
保证会指向两个不同、单独的新建空列表。(请注意c = d = []
则是将同一个对象赋值给c
和d
。)
至此真相大白。
解决方案
可以使用列表生成式创建二维列表:
1 | # Solution 1 |
类似操作也可使用 numpy
库更为简便:
1 | import numpy as np |
以上。