3秒でわかる
点と線のつながりだけで対象を表すデータ構造。経路探索や関係の追跡に使い、路線図や友人関係のような循環のある関係を素直に扱えます。
もう少し詳しく
どういうものか
グラフはノード（頂点）とエッジ（辺）だけで対象を表すデータ構造です。ノードが駅、エッジが線路と考えると分かりやすく、どのノードからどのノードへ線を引いてもよいのが特徴です。エッジに向きがあるものを有向グラフ、向きがないものを無向グラフ、エッジに数値を持たせたものを重み付きグラフと呼びます。
木構造との違いは、閉じた輪を許すかどうかにあります。木は親が一つで循環がありませんが、グラフは A から B、B から C、C から A と戻ってこられます。つまり木はグラフの特別な形の一つです。
なぜ必要か
現実の関係の多くは一本道でも階層でもありません。乗換案内の最短経路、SNS の友達の友達、依存パッケージのインストール順、Web ページ同士のリンク、工程の前後関係。これらを配列や表で持つと「たどる」処理のたびに全走査が必要になりますが、グラフとして持てば隣接ノードの一覧を引くだけで済みます。
具体例
隣接リストは辞書で素直に書けます。幅優先探索で最短の乗り換え回数を求める例です。
from collections import deque
lines = {
"shinjuku": ["yoyogi", "shibuya"],
"yoyogi": ["shinjuku", "harajuku"],
"harajuku": ["yoyogi", "shibuya"],
"shibuya": ["shinjuku", "harajuku"],
}
def hops(start, goal):
seen = {start}
q = deque([(start, 0)])
while q:
node, d = q.popleft()
if node == goal:
return d
for nxt in lines[node]:
if nxt not in seen:
seen.add(nxt)
q.append((nxt, d + 1))
return -1
print(hops("shinjuku", "harajuku"))
