グラフ（隣接する頂点）

March 12, 2023

問題

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

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

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

[制約]
🔹 $2 ≦ N ≦ 100000$
🔹 $1 ≦ M ≦ 100000$
🔹 $1 ≦ A_{i} < B_{i} ≦ N$

解き方・ソースコード

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

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

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

[Google Colaboratory]

#-------- 入力例１ ---------
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]

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