グラフ - データサイエンス関連+αのメモ

グラフ（Graph） は、頂点（ノード, vertex） と 辺（エッジ, edge） からなるデータ構造

G = (V, E)

(1)

$V$ ：頂点の集合
$E$ ：辺の集合（頂点のペア）

現実世界の多くの問題をグラフとしてモデル化できる（地図・道路網、SNSの友人関係、タスクの依存関係など）

グラフの種類¶

種類	説明
無向グラフ（Undirected）	辺に向きがない。 $(u, v)$ と $(v, u)$ は同じ辺
有向グラフ（Directed, Digraph）	辺に向きがある。 $(u, v)$ と $(v, u)$ は別の辺
重み付きグラフ（Weighted）	各辺にコスト（重み）が付いている
DAG（有向非巡回グラフ）	有向グラフで閉路（サイクル）がないもの
木（Tree）	連結で閉路のない無向グラフ。$

グラフの表現方法¶

隣接行列（Adjacency Matrix）¶

$|V| \times |V|$ の行列 $A$ で表す。 $A[u][v] = 1$ （または重み）なら辺 $(u, v)$ が存在する

辺の存在確認： $O(1)$
隣接頂点の列挙： $O(|V|)$
空間計算量： $O(|V|^2)$ （疎なグラフには非効率）

隣接リスト（Adjacency List）¶

各頂点が隣接する頂点のリストを持つ

辺の存在確認： $O(\deg(u))$
隣接頂点の列挙： $O(\deg(u))$
空間計算量： $O(|V| + |E|)$ （疎なグラフに効率的）

from collections import defaultdict, deque


class Graph:
    """隣接リストによる無向グラフ"""

    def __init__(self):
        self.adj = defaultdict(list)

    def add_edge(self, u, v):
        self.adj[u].append(v)
        self.adj[v].append(u)

    def neighbors(self, u):
        return self.adj[u]

    def vertices(self):
        return list(self.adj.keys())


class WeightedGraph:
    """隣接リストによる重み付き有向グラフ"""

    def __init__(self):
        self.adj = defaultdict(list)  # adj[u] = [(v, weight), ...]

    def add_edge(self, u, v, weight=1):
        self.adj[u].append((v, weight))

    def neighbors(self, u):
        return self.adj[u]

# グラフの構築例
# 0 - 1 - 2
# |       |
# 3 ----- 4
g = Graph()
for u, v in [(0, 1), (1, 2), (2, 4), (0, 3), (3, 4)]:
    g.add_edge(u, v)

print("頂点0の隣接頂点:", g.neighbors(0))
print("頂点2の隣接頂点:", g.neighbors(2))

幅優先探索（BFS）¶

始点から近い頂点から順に探索する。キューを使う

計算量： $O(|V| + |E|)$
用途：最短経路（辺の重みが均一な場合）、連結成分の判定

def bfs(graph: Graph, start):
    """BFS で始点から各頂点への最短距離を返す"""
    dist = {start: 0}
    queue = deque([start])

    while queue:
        u = queue.popleft()
        for v in graph.neighbors(u):
            if v not in dist:
                dist[v] = dist[u] + 1
                queue.append(v)

    return dist


dist = bfs(g, 0)
print("頂点0からの最短距離:", dist)

深さ優先探索（DFS）¶

できる限り深く探索してから戻る。スタック（または再帰）を使う

計算量： $O(|V| + |E|)$
用途：連結成分の判定、トポロジカルソート、閉路検出

def dfs(graph: Graph, start):
    """DFS で到達できる頂点を返す"""
    visited = set()
    order = []

    def _dfs(u):
        visited.add(u)
        order.append(u)
        for v in graph.neighbors(u):
            if v not in visited:
                _dfs(v)

    _dfs(start)
    return order


print("DFS 訪問順（始点=0）:", dfs(g, 0))

トポロジカルソート¶

DAG（有向非巡回グラフ）の頂点を、すべての辺 $(u, v)$ において $u$ が $v$ より前になるよう並べる

タスクの依存関係の解決やビルドシステムなどに使われる

カーン法（Kahn’s algorithm）を使う：入次数（in-degree）が 0 の頂点をキューに入れ、順番に取り出す

計算量： $O(|V| + |E|)$

def topological_sort(adj: dict, vertices: list) -> list | None:
    """カーン法によるトポロジカルソート。閉路があれば None を返す"""
    in_degree = defaultdict(int)
    for u in vertices:
        for v in adj[u]:
            in_degree[v] += 1

    queue = deque([u for u in vertices if in_degree[u] == 0])
    result = []

    while queue:
        u = queue.popleft()
        result.append(u)
        for v in adj[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)

    return result if len(result) == len(vertices) else None


# タスクの依存関係: A→C, B→C, C→D
dag_adj = defaultdict(list, {"A": ["C"], "B": ["C"], "C": ["D"], "D": []})
vertices = ["A", "B", "C", "D"]
print("トポロジカルソート:", topological_sort(dag_adj, vertices))

ダイクストラ法¶

重み付きグラフで、始点から各頂点への最短経路を求める

辺の重みが非負であることが前提
計算量：優先度付きキューを使うと $O((|V| + |E|) \log |V|)$
用途：地図アプリの経路探索、ネットワークのルーティング

import heapq


def dijkstra(graph: WeightedGraph, start):
    """始点から各頂点への最短距離を返す"""
    dist = defaultdict(lambda: float("inf"))
    dist[start] = 0
    heap = [(0, start)]  # (距離, 頂点)

    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue
        for v, w in graph.neighbors(u):
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(heap, (dist[v], v))

    return dict(dist)


# 重み付きグラフの例
wg = WeightedGraph()
for u, v, w in [(0, 1, 4), (0, 2, 1), (2, 1, 2), (1, 3, 1), (2, 3, 5)]:
    wg.add_edge(u, v, w)

print("頂点0からの最短距離:", dijkstra(wg, 0))

まとめ¶

アルゴリズム	計算量	用途
BFS	$O(	V
DFS	$O(	V
トポロジカルソート（カーン法）	$O(	V
ダイクストラ法	$O((	V

グラフ表現の選択

密なグラフ（ $|E| \approx |V|^2$ ）→ 隣接行列が有利（辺の存在を $O(1)$ で確認）
疎なグラフ（ $|E| \ll |V|^2$ ）→ 隣接リストが有利（空間効率が良い）

競技プログラミングやシステム設計では疎なグラフが多いため、隣接リストが一般的