はじめに
競技プログラミングを行っていると、遅かれ早かれぶつかる壁が「グラフ理論」です。今回はPythonでの「隣接行列 (Adjacency matrix) 」と「隣接リスト (Adjacency list) 」の基本の作成方法をコード付きでまとめました。問題によっては自身の手で変形してください。
隣接行列と隣接リスト
例えば、以下のようなグラフを考えます。
コンピュータ上でのグラフのデータ構造は大きく2種類あります。状況に応じて使い分けましょう。
一つは隣接行列で、$n\times n$ の行列形式になります。メモリの使用量が多いですが、定数時間で特定の辺があるかどうかを判別できるというメリットがあります。
adj_m.txt
[[0, 1, 1, 0, 1],
[1, 0, 1, 1, 0],
[1, 1, 0, 1, 1],
[0, 0, 1, 1, 1],
[1, 0, 1, 1, 0]]
もう一つは隣接リストです。メモリの使用量が少ない反面、特定の辺があるかどうかの判定に、最悪 $O(V)$ の時間がかかるというデメリットがあります。
adj_l.txt
[[2, 3, 5], [1, 3, 4], [1, 2, 4, 5], [2, 3, 5], [1, 3, 4]]
実際の問題では、AtCoder Beginners Contest 168 D .. (Double Dots)のような、辺の2つの端点が与えられることが多いです。
今回のグラフに対する入力を表現しようとすると以下のようになります。(1行目に頂点の数nと辺の数mが入力されています)
input.txt
5 8
1 2
1 3
1 5
2 3
2 4
3 4
3 5
4 5
Pythonコード
入力の隣接行列と隣接リストへの変換とそれらの相互変換のチートシートを書いていきます。
入力 to 隣接リスト
辺の重みがない場合。
n, m = map(int, input().split())
graph = [[] for _ in range(n)]
for _ in range(m):
a, b = map(int, input().split())
graph[a-1].append(b-1)
graph[b-1].append(a-1) # 有向グラフなら消す
print(graph) # [[2, 3, 5], ..., [1, 3, 4]]
辺の重みがある場合。
n, m = map(int, input().split())
graph = [[] for _ in range(n)]
for _ in range(n):
u, v, w = map(int, input().split())
graph[u-1].append([v-1, w])
graph[v-1].append([u-1, w]) # 有向グラフなら消す
print(graph) # [[2, 3], [3, 1], [5, 9]], ..., [...]]
入力 to 隣接行列
辺の重みがない場合。
n, m = map(int, input().split())
graph = [[0]*n for _ in range(n)]
for _ in range(m):
a, b = map(int, input().split())
graph[a-1][b-1] = 1
graph[b-1][a-1] = 1 # 有向グラフなら消す
print(graph) # [[0, 1, 1, 0, 1], ..., [1, 0, 1, 1, 0]]
重み有りの場合。
n, m = map(int, input().split())
graph = [[0]*n for _ in range(n)]
for _ in range(m):
u, v, w = map(int, input().split())
graph[u-1][v-1] = w
graph[v-1][u-1] = w # 有向グラフなら消す
print(graph) # [[0, 2, 3, 0, 1], ..., [2, 0, 3, 0, 0]
隣接リスト to 隣接行列
辺の重みがない無向グラフを対象としています。
隣接リストがgraph、隣接行列がgraph_newです。
graph_new = [[0]*n for _ in range(n)] # 隣接行列
for i, g_i in enumerate(graph):
for j in g_i:
graph_new[i][j] = 1
print(graph_new)
隣接行列 to 隣接リスト
辺の重みがない無向グラフを対象としています。
隣接行列がgraph、隣接リストがgraph_newです。
graph_new = []
for i in range(n):
tmp_l = []
for j in range(n):
if graph[i][j] > 0:
tmp_l.append(j)
graph_new.append(tmp_l)
print(graph_new)
おわりに
お読み頂きありがとうございました。間違いや誤字等があれば教えて頂けると嬉しいです。