グラフ（隣接する頂点）

問題

頂点数 $N$、辺数 $M$ のグラフがあります。

頂点には $1$ から $N$ までの番号が付けられており、$i$ 番目の辺は頂点 $A_i$ と $B_i$ を双方向に結んでいます。

それぞれの頂点 $k$ について隣接している頂点の番号をすべて出力して下さい。

[制約]
🔹$ 2 \leqq N \leqq 100000 $
🔹$ 1 \leqq M \leqq 100000 $
🔹$ 1 \leqq A_i < B_i \leqq N $

解き方・ソースコード

この問題は、隣接リストを作成する問題です。

隣接リストは、各頂点に対して隣接する頂点のリストを記録する方法です。

隣接リストは、メモリ使用量が少ないことが大きな特徴です。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#-------- 入力例１ ---------
N = 5       # 頂点の数
M = 4       # 辺の数
edges = [(1, 3), (2, 4), (3, 4), (3, 5)]    # 隣接する頂点の組み合わせ
#---------------------------
# 隣接リストの作成
G = [ list() for i in range(N + 1) ] # G[i] は頂点 i に隣接する頂点のリスト
for a, b in edges:
    G[a].append(b) # 頂点 a に隣接する頂点として b を追加
    G[b].append(a) # 頂点 b に隣接する頂点として a を追加

# 頂点ごとに隣接する頂点を出力
for i in range(1, N + 1):
    print('{}; [{}]'.format(i, ', '.join(map(str, G[i]))))

[実行結果（入力例１）]

1; [3]

2; [4]

3; [1, 4, 5]

4; [2, 3]

5; [3]

各頂点に隣接している頂点の番号（隣接リスト）を作成・表示することができました。