HOWTO · Python
Python の隣接行列
この記事では、Python での重み付きグラフと重みなしグラフの隣接行列の実装について説明します。
このページの内容
グラフ データ構造は、Python でネットワークやマップなどのさまざまな現実のオブジェクトを表すために使用されます。 隣接行列を使用してグラフを表すことができます。
この記事では、Python で隣接行列を実装するさまざまな方法について説明します。
隣接行列の作成
次のグラフを考えてみましょう。
グラフには、1 から 6 までの番号が付けられた 6つのノードがあります。グラフには、ノードを接続する 7つのエッジがあります。 エッジ eij は、ノード i とノード j を接続します。
グラフを表すために、隣接行列を使用します。
- 隣接行列は、2 次元グリッドで構成されます。
- グリッドの各行または列はノードを表します。
- 上に示すように、重み付けされていないグラフの場合、グリッド内の位置
(i,j)の値が 1 の場合、ノードiとノードjが接続されていることを意味します。 - 位置
(i,j)の値が 0 の場合、ノードiとノードjは接続されていません。
上の画像のグラフの隣接行列を作成する場合は、次のようになります。
| 0 | 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 | 1 | 0 |
| 0 | 0 | 0 | 1 | 0 | 1 |
| 0 | 0 | 1 | 0 | 1 | 0 |
上の表は、位置 (i,j) の値が位置 (j,i) にも存在することを示しています。 これは、エッジ eij がエッジ eji と同じであるためです。
これにより、対角線に沿って対称な隣接行列も得られます。
重み付けされていないグラフでは、エッジに重みがありません。 つまり、すべてのエッジの重みが等しくなります。
このため、隣接行列には値 0 と 1 のみが含まれます。
ここで、次の加重グラフを考えてみましょう。
重み付きグラフの場合、エッジの重みを除いてすべて同じままです。 イメージ内の各エッジに値が割り当てられていることがわかります。
したがって、隣接行列では、位置 (i,j) の値は、グラフ内のエッジ eij の重みです。
上の画像の隣接行列は次のようになります。
| 0 | 5 | 0 | 0 | 0 | 0 |
| 5 | 0 | 1 | 12 | 0 | 0 |
| 0 | 1 | 0 | 8 | 0 | 4 |
| 0 | 12 | 8 | 0 | 7 | 0 |
| 0 | 0 | 0 | 7 | 0 | 2 |
| 0 | 0 | 4 | 0 | 2 | 0 |
ここでも、行列内の位置 (i,j) の値が位置 (j,i) にも存在することがわかります。 これは、エッジ eij がエッジ eji と同じであるためです。
繰り返しますが、これにより対角線に沿った対称隣接行列が得られます。
2D リストを使用して Python で隣接行列を作成する
n 個のノードを持つ重み付けされていないグラフの隣接行列を作成するには、まず n 個の内部リストを含む 2 次元リストを作成します。 さらに、各内部リストには n 個のゼロが含まれます。
ゼロを含む 2 次元のリストを作成した後、グラフ内でエッジ eij が存在する位置 (i,j) に 1 を割り当てます。 このタスクでは、次の手順を使用します。
-
まず、
adjacency_matrixという名前の空のリストを作成します。 その後、forループとappend()メソッドを使用して 2 次元リストに変換します。 -
forループ内で、rowという名前の空のリストを作成します。 次に、別のforループを使用して空のリストにゼロを入力し、最後にrowをadjacency_matrixに追加します。 -
コードでは、タプルのリストを使用してエッジのセットを表現しました。 各タプルには、グラフの接続されたノードを表す 2つの値が含まれています。
-
エッジを定義した後、
forループを使用して、グラフ内のエッジが存在する位置に値 1 を割り当てます。
コード：
import pprint
row_num = 6
col_num = 6
adjacency_matrix = []
for i in range(row_num):
row = []
for j in range(col_num):
row.append(0)
adjacency_matrix.append(row)
edges = [(1, 2), (2, 4), (2, 3), (3, 4), (4, 5), (3, 6), (5, 6)]
for edge in edges:
row = edge[0]
col = edge[1]
adjacency_matrix[row - 1][col - 1] = 1
adjacency_matrix[col - 1][row - 1] = 1
print("The edges in the graph are:")
print(edges)
print("The adjacency matrix is:")
pprint.pprint(adjacency_matrix)
出力：
The edges in the graph are:
[(1, 2), (2, 4), (2, 3), (3, 4), (4, 5), (3, 6), (5, 6)]
The adjacency matrix is:
[[0, 1, 0, 0, 0, 0],
[1, 0, 1, 1, 0, 0],
[0, 1, 0, 1, 0, 1],
[0, 1, 1, 0, 1, 0],
[0, 0, 0, 1, 0, 1],
[0, 0, 1, 0, 1, 0]]
コードでは、0 から始まるインデックス付けが行われていることがわかります。 このため、各ノード (i,j) は隣接行列の位置 (i-1,j-1) で表されます。
加重グラフの隣接行列を作成するには、最初に 0 を持つ n x n 2 次元リストを作成します。 その後、行列の位置 (i,j) でエッジ eij の重みを割り当てます。
これは、次の例で確認できます。
import pprint
row_num = 6
col_num = 6
adjacency_matrix = []
for i in range(row_num):
row = []
for j in range(col_num):
row.append(0)
adjacency_matrix.append(row)
weighted_edges = [
(1, 2, 5),
(2, 4, 12),
(2, 3, 1),
(3, 4, 8),
(4, 5, 7),
(3, 6, 4),
(5, 6, 2),
]
for edge in weighted_edges:
row = edge[0]
col = edge[1]
weight = edge[2]
adjacency_matrix[row - 1][col - 1] = weight
adjacency_matrix[col - 1][row - 1] = weight
print("The edges in the graph are:")
print(weighted_edges)
print("The adjacency matrix is:")
pprint.pprint(adjacency_matrix)
出力：
The edges in the graph are:
[(1, 2, 5), (2, 4, 12), (2, 3, 1), (3, 4, 8), (4, 5, 7), (3, 6, 4), (5, 6, 2)]
The adjacency matrix is:
[[0, 5, 0, 0, 0, 0],
[5, 0, 1, 12, 0, 0],
[0, 1, 0, 8, 0, 4],
[0, 12, 8, 0, 7, 0],
[0, 0, 0, 7, 0, 2],
[0, 0, 4, 0, 2, 0]]
上記のコードでは、エッジは 3つの数値を使用して表現されています。 最初の 2つの数字は、エッジで接続されているグラフのノードを表します。
3 番目の数値はエッジの重みを表します。
NumPy モジュールを使用して Python で隣接行列を作成する
NumPy モジュールを使用してグラフの隣接行列を作成するには、np.zeros() メソッドを使用できます。
np.zeros() メソッドは、入力引数として (row_num,col_num) の形式のタプルを取り、形状 row_num x col_num の 2 次元マトリックスを返します。 ここで、row_num と col_num は行列の行と列の数です。
次の手順を使用して、np.zeros() メソッドを使用して隣接行列を作成します。
-
最初に、タプル
(n,n)をzeros()メソッドに渡すことにより、サイズn x nの行列を作成します。 -
次に、グラフのすべてのエッジ eij の位置
(i-1,j-1)で値を 1 に更新します。 ここでは、0 ベースのインデックスを使用します。 このため、ノード(i,j)はコード内の位置(i-1,j-1)で表されます。
上記の手順を実行すると、次の例に示すように、隣接行列が取得されます。
import pprint
import numpy as np
row_num = 6
col_num = 6
adjacency_matrix = np.zeros((row_num, col_num), dtype=int)
edges = [(1, 2), (2, 4), (2, 3), (3, 4), (4, 5), (3, 6), (5, 6)]
for edge in edges:
row = edge[0]
col = edge[1]
adjacency_matrix[row - 1][col - 1] = 1
adjacency_matrix[col - 1][row - 1] = 1
print("The edges in the graph are:")
print(edges)
print("The adjacency matrix is:")
pprint.pprint(adjacency_matrix)
出力：
The edges in the graph are:
[(1, 2), (2, 4), (2, 3), (3, 4), (4, 5), (3, 6), (5, 6)]
The adjacency matrix is:
array([[0, 1, 0, 0, 0, 0],
[1, 0, 1, 1, 0, 0],
[0, 1, 0, 1, 0, 1],
[0, 1, 1, 0, 1, 0],
[0, 0, 0, 1, 0, 1],
[0, 0, 1, 0, 1, 0]])
重み付きグラフの隣接行列を作成するには、以下に示すように、位置 (i,j) の値をエッジ eij の重みに更新します。
import pprint
import numpy as np
row_num = 6
col_num = 6
adjacency_matrix = np.zeros((row_num, col_num), dtype=int)
weighted_edges = [
(1, 2, 5),
(2, 4, 12),
(2, 3, 1),
(3, 4, 8),
(4, 5, 7),
(3, 6, 4),
(5, 6, 2),
]
for edge in weighted_edges:
row = edge[0]
col = edge[1]
weight = edge[2]
adjacency_matrix[row - 1][col - 1] = weight
adjacency_matrix[col - 1][row - 1] = weight
print("The edges in the graph are:")
print(weighted_edges)
print("The adjacency matrix is:")
pprint.pprint(adjacency_matrix)
出力：
The edges in the graph are:
[(1, 2, 5), (2, 4, 12), (2, 3, 1), (3, 4, 8), (4, 5, 7), (3, 6, 4), (5, 6, 2)]
The adjacency matrix is:
array([[ 0, 5, 0, 0, 0, 0],
[ 5, 0, 1, 12, 0, 0],
[ 0, 1, 0, 8, 0, 4],
[ 0, 12, 8, 0, 7, 0],
[ 0, 0, 0, 7, 0, 2],
[ 0, 0, 4, 0, 2, 0]])
まとめ
この記事では、Python で隣接行列を実装する 2つの方法について説明します。 NumPy モジュールを使用して隣接行列を実装することをお勧めします。これは、ストレージ要件に関してはるかに効率的であるためです。
また、NumPy 配列に対してさまざまな操作を実行すると、時間とメモリの要件に関してはるかに効率的になります。
