グラフ

グラフ#

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

\[G = (V, E)\]

  • \(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))

頂点0の隣接頂点: [1, 3]
頂点2の隣接頂点: [1, 4]

幅優先探索（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)

頂点0からの最短距離: {0: 0, 1: 1, 3: 1, 2: 2, 4: 2}

深さ優先探索（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))

DFS 訪問順（始点=0）: [0, 1, 2, 4, 3]

トポロジカルソート#

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))

トポロジカルソート: ['A', 'B', 'C', 'D']

ダイクストラ法#

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

  • 辺の重みが非負であることが前提

  • 計算量：優先度付きキューを使うと \(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))

頂点0からの最短距離: {0: 0, 1: 3, 2: 1, 3: 4}

まとめ#

アルゴリズム

計算量

用途

BFS

$O(

V

DFS

$O(

V

トポロジカルソート（カーン法）

$O(

V

ダイクストラ法

$O((

V
グラフ表現の選択

  • 密なグラフ（\(|E| \approx |V|^2\)）→ 隣接行列が有利（辺の存在を \(O(1)\) で確認）

  • 疎なグラフ（\(|E| \ll |V|^2\)）→ 隣接リストが有利（空間効率が良い）

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

Contents