3

Pythonで隣接行列を表現しようとしたら2次元配列が期待と異なる挙動をしてしまったため、どういう理由でこういう挙動になったのか?どうするのがよいのか?の二点を質問させてください。

やりたいこと

無向グラフを隣接行列で表現したい。
リンクが有るところは1で、ないところは0にしたい。
最初にノードの数がわかるので、0で2次元配列Aを初期化したい。
初期化の方法で下記のAのような方法をとった。

挙動

A = [[0] * 3] * 3
# A = [[0, 0, 0], [0, 0, 0], [0, 0, 0]]

試しに1つだけリンクを追加してみる
A[0][1] = 1
# [[0, 1, 0], [0, 1, 0], [0, 1, 0]]

期待する動作

A[0][1] = 1としたら、
[[0, 1, 0], [0, 0, 0], [0, 0, 0]]
となると期待

(ちなみに)

B = [[0,0,0],[0,0,0],[0,0,0]]
として同じことをやると
# [[0, 1, 0], [0, 0, 0], [0, 0, 0]]
となってくれて期待通りに動いてくれます。
が、これだとノードの数がわかっても動的に隣接行列を初期化できないためこの方法はとりたくない。

よろしくおねがいします。

1

2 件の回答 2

4

A = [[0] * 3] * 3と言うのは、ほぼ次のようなコードと等価だと言えば少し理解しやすくなるでしょうか。

c = 0
b = [c,c,c]
A = [b,b,b]

Pythonのリストは参照で保持されます。* 3という演算ではその参照がコピーされるだけなので、

A = [[0] * 3] * 3という式では、内側のリスト[0, 0, 0]は一つだけ作られて、A[0], A[1], A[2]のどれもが同じリストを参照することになるのです。

例えばこんな書き方をすると、お望みの動作になると思います。

>>> A = [[0 for j in range(3)] for i in range(3)]
>>> A
[[0, 0, 0], [0, 0, 0], [0, 0, 0]]
>>> A[0][1] = 1
>>> A
[[0, 1, 0], [0, 0, 0], [0, 0, 0]]

内側の方は、*を使って、A = [[0]*3 for i in range(3)]でも良い(*が評価されるたびに新しいリストを作るため)んですが、少し分かりにくいかもしれません。

1

以下のようにfor文等でappendを必要な回数繰り返されたらどうでしょうか?

※すみません、pythonらしい書き方を知りません。
※提示されているAとBの様子(構造)の違いを表示させたかったのですが、当然、typeではどうにもならず。でした。

追記:
 以下のようにid()関数で、確認できるようです。
 A[0]とA[1]は、同じものである、idが同じであることがわかります。
 イミュータブル等の説明で、こうなることは、一部、納得できる。

 >>> A=[[0]*3]*3
 >>> A
 [[0, 0, 0], [0, 0, 0], [0, 0, 0]]
 >>> id(A[0])
 1639979327816
 >>> id(A[1])
 1639979327816
 >>>

参考:
 https://qiita.com/utgwkk/items/5ad2527f19150ae33322

※元の現象は、listの__mul__()のコードを見れば理解できるのかもしれません。

>>> out_a = []
>>> req_n = 5
>>> for x in range(0,req_n-1):
...   out_a.append([0,0,0])
...
>>> out_a
[[0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0]]
>>> out_a[0][1] = 1
>>> out_a
[[0, 1, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0]]
>>>
1
  • n回繰り返すためには、単にrange(n)と書くとrange(0, n)の意味になります :)
    – nekketsuuu
    Commented 2019年4月21日 2:13

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。