[Python] defaultdict を使った隣接リスト

隣接リスト

グラフを表現する方法に隣接リストがあります。

ここでは、defaultdict オブジェクトを使うことで、より簡単に隣接リストを表現することを考えます。

`defaultdict` オブジェクト

ほとんと辞書と同じですが、存在しないキーを参照した時に例外が起こらず、デフォルト値が入った状態にしてくれます。

新しいキーの追加が、標準の辞書に比べて簡単に行えます。

D – バスと避けられない運命

上の例題で、隣接リストを作成します。

辺の重みのある無向グラフの問題で、ダイクストラ法が使えます。

N, M = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(M)]

adjacent_list = [[] for _ in range(N+1)]
for frm, to, weight in edges:
    adjacent_list[frm].append((to, weight))
    adjacent_list[to].append((frm, weight))

# [[], [(2, 10)], [(1, 10), (3, 10)], [(2, 10)]]
print(adjacent_list)

辞書

辞書を用いて、隣接リストを表現します。

N, M = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(M)]

adjacent_dict = dict()

for frm, to, weight in edges:
    if frm not in adjacent_dict:
        adjacent_dict[frm] = []
    adjacent_dict[frm].append([to, weight])
    if to not in adjacent_dict:
        adjacent_dict[to] = []
    adjacent_dict[to].append([frm, weight])

# {1: [[2, 10]], 2: [[1, 10], [3, 10]], 3: [[2, 10]]}
print(adjacent_dict)

`defaultdict`

defaultdict を用いて、隣接リストを表現します。

 N, M = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(M)]

import collections

adjacent_dict = collections.defaultdict(list)

for frm, to, weight in edges:
    adjacent_dict[frm].append([to, weight])
    adjacent_dict[to].append([frm, weight])

# defaultdict(<class 'list'>, {1: [[2, 10]], 2: [[1, 10], [3, 10]], 3: [[2, 10]]})
print(adjacent_dict)

リストと比較すると、初期化がシンプルで、0インデックスを考える必要がなく、より直感的です。

辞書と比較すると、辞書にキーがない場合の場合分けをする必要がなく、コードがすっきりしています。

隣接リスト

defaultdict オブジェクト

D – バスと避けられない運命

リスト

辞書

defaultdict

`defaultdict` オブジェクト

`defaultdict`