目次を表示する

CS基礎：計算量とデータ構造

グラフの表現とトラバーサル ── BFS / DFS / トポロジカルソート

グラフの表現とトラバーサル ── BFS / DFS / トポロジカルソート

扱う概念：隣接リスト / 隣接行列、BFS（幅優先）/ DFS（深さ優先）、トポロジカルソート、Union-Find（素集合）、サイクル検出

グラフアルゴリズム — BFS・DFS・トポロジカルソート・Union-Find

この章で何ができるようになるか：グラフ問題を見たときに「BFS か DFS か」を判断でき、依存関係の解決（トポロジカルソート）や連結成分の検出（Union-Find）を実装できるようになる。

グラフの表現

# 隣接リスト（最も一般的）
graph = {
    0: [1, 2],
    1: [0, 3],
    2: [0, 3],
    3: [1, 2],
}
# メモリ: O(V + E)、エッジ検索: O(degree)

# 隣接行列
matrix = [
    [0, 1, 1, 0],
    [1, 0, 0, 1],
    [1, 0, 0, 1],
    [0, 1, 1, 0],
]
# メモリ: O(V²)、エッジ検索: O(1)
# 密グラフでないかぎり隣接リストが効率的

BFS（幅優先探索）

「層ごと」に探索する。最短経路（重みなしグラフ）を求めるときに使う。

from collections import deque

def bfs_shortest_path(graph: dict, start: int, end: int) -> int:
    """start から end までの最短距離（辺の数）を返す"""
    if start == end:
        return 0
    visited = {start}
    queue = deque([(start, 0)])

    while queue:
        node, dist = queue.popleft()
        for neighbor in graph[node]:
            if neighbor == end:
                return dist + 1
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, dist + 1))

    return -1  # 到達不能

# 計算量: O(V + E)

BFS の応用：多始点 BFS

「全ての門から同時にスタートして、各セルまでの最短距離を求める」（01-BFS、腐ったオレンジ問題）。

def oranges_rotting(grid: list[list[int]]) -> int:
    """腐ったオレンジが隣の新鮮なオレンジを腐らせる最短時間"""
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh = 0

    # 全ての腐ったオレンジを初期キューに入れる（多始点BFS）
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c, 0))
            elif grid[r][c] == 1:
                fresh += 1

    minutes = 0
    for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        pass  # placeholder

    while queue:
        r, c, t = queue.popleft()
        for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                grid[nr][nc] = 2
                fresh -= 1
                minutes = t + 1
                queue.append((nr, nc, t + 1))

    return minutes if fresh == 0 else -1

DFS（深さ優先探索）

「行けるところまで深く進み、行き止まりで戻る」。再帰 or スタックで実装。

def dfs_recursive(graph: dict, node: int, visited: set = None):
    if visited is None:
        visited = set()
    visited.add(node)
    print(node, end=" ")
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)

# 計算量: O(V + E)

DFS の応用：島の数（Number of Islands）

def num_islands(grid: list[list[str]]) -> int:
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])
    count = 0

    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != '1':
            return
        grid[r][c] = '0'  # 訪問済みマーク
        dfs(r - 1, c)
        dfs(r + 1, c)
        dfs(r, c - 1)
        dfs(r, c + 1)

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                dfs(r, c)
                count += 1
    return count

BFS vs DFS の選択基準

BFSDFS
最短経路✅ 重みなしグラフの最短経路❌ 最短とは限らない
メモリO(幅)（幅が広いと大量）O(深さ)（深いと大量）
全探索○○
サイクル検出○✅ より自然（バックエッジ検出）
迷路の最短解✅❌
全パス列挙❌✅（バックトラッキング）

トポロジカルソート

**DAG（有向非巡回グラフ）**の頂点を、全ての辺が「左から右」になるように並べる。

ビルドの依存関係：
  A → B → D
  A → C → D
  
トポロジカル順序: A, B, C, D（または A, C, B, D）
from collections import deque

def topological_sort(graph: dict[int, list[int]], num_nodes: int) -> list[int]:
    """Kahn のアルゴリズム（BFS ベース）"""
    in_degree = [0] * num_nodes
    for node in graph:
        for neighbor in graph[node]:
            in_degree[neighbor] += 1

    # 入次数0のノードをキューに入れる
    queue = deque(i for i in range(num_nodes) if in_degree[i] == 0)
    result = []

    while queue:
        node = queue.popleft()
        result.append(node)
        for neighbor in graph.get(node, []):
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    if len(result) != num_nodes:
        raise ValueError("Graph has a cycle")  # サイクルがあるとソートできない

    return result

使用例：ビルドシステムの依存解決、大学の履修科目の順序決定、タスクスケジューリング。

Union-Find（素集合データ構造）

「この2つのノードは同じグループか？」を高速に判定する。

class UnionFind:
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.count = n  # 連結成分数

    def find(self, x: int) -> int:
        """ルートを返す（経路圧縮あり）"""
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # 経路圧縮
        return self.parent[x]

    def union(self, x: int, y: int) -> bool:
        """2つの要素を同じグループにする（ランクによる結合）"""
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False  # 既に同じグループ
        # ランクが低い方を高い方に接続
        if self.rank[rx] < self.rank[ry]:
            rx, ry = ry, rx
        self.parent[ry] = rx
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1
        self.count -= 1
        return True

    def connected(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)

計算量：find / union ともに償却 O(α(n)) ≈ O(1)（α はアッカーマン関数の逆関数、実質的に定数）。

使用例：Kruskal の最小全域木、ネットワークの連結判定、ソーシャルグラフの「同じコミュニティか」判定。

まとめ

アルゴリズム計算量主な用途
BFSO(V + E)最短経路（重みなし）、レベル順探索
DFSO(V + E)全パス列挙、サイクル検出、連結成分
トポロジカルソートO(V + E)依存解決、タスクスケジューリング
Union-FindO(α(n)) ≈ O(1)連結判定、最小全域木
DijkstraO((V+E) log V)最短経路（重みあり）