グラフ — Project Hematite

連結リストはノードを一本の鎖でつなぐ — 各ノードは直後の後継しか知らない。しかし現実の問題の多くは、鎖より豊かな関係を持つ。交差点が四方八方に枝分かれする道路網、複数の仕事に依存するビルドシステム、誰でも誰かと繋がれるソーシャルネットワーク。これらすべてをモデル化する構造がグラフ（graph）であり、コンピュータサイエンスで最も重要なアルゴリズム群の中心に位置する。

グラフとは何か

グラフ $G$ は 2 つの集合からなる：

$V$ — 頂点（vertex）の集合。モデル化する対象を表す。ノード（node）とも呼ぶ。
$E$ — 辺（edge）の集合。各辺は頂点のペアを結び、その間の関係を表す。

$G = (V, E)$ と書く。

具体例として、4 つの都市とそれらをつなぐ道路を考える：

V = \{A, B, C, D\}

E = \{(A, B),\; (A, C),\; (B, D),\; (C, D)\}

A ──── B
│      │
C ──── D

頂点数を $|V|$ 、辺数を $|E|$ と書く。この 2 つの量がすべてのグラフアルゴリズムの時間・空間計算量を左右する。

有向グラフと無向グラフ

上の都市の例では、すべての道路が双方向だ — $A$ から $B$ に行けるなら $B$ から $A$ にも行ける。これが無向グラフ（undirected graph）だ。各辺は対称な接続であり、ペア $(u, v)$ と $(v, u)$ は同じ辺を指す。

有向グラフ（directed graph）、別名有向グラフ（digraph）は各辺に方向を持たせる。辺 $(u, v)$ は「 $u$ から $v$ へ」のみを意味し、逆方向の $(v, u)$ は別の辺であって存在しないこともある。

無向：                有向：
  A ─── B              A ──► B
  │     │              │
  C ─── D              ▼
                        C ──► D

有向グラフは一方通行の道路、タスクの依存関係、データパイプライン、方向が意味を持つあらゆる関係のモデル化に使われる。

重み付きグラフと重み無しグラフ

ここまでの辺は存在するかしないかだけだった。重み付きグラフ（weighted graph）は各辺に数値の重み（weight）を付与する — 距離、コスト、容量、あるいは問題に応じた任意の測定値だ。

    5        2
A ───── B ───── D
│               │
│  3            │ 1
│               │
C ──────────────┘
         4

2 都市間の最短ドライブルートを求めるなら辺の重みは距離、最安フライト経路を求めるなら航空券の価格になる。重み無しグラフ（unweighted graph）は全辺の重みが 1 の重み付きグラフとして扱える。

次数

次数（degree）は頂点に接続する辺の数を数える。

無向グラフでは、頂点 $v$ の次数 $\deg(v)$ は $v$ に接続する辺の数だ。
有向グラフでは次数が 2 種類に分かれる：
- 入次数（in-degree）： $v$ に向かう辺の数。
- 出次数（out-degree）： $v$ から出る辺の数。

次数 0 の頂点は孤立点（isolated vertex）と呼ばれ、隣接頂点を持たない。

無向グラフでは全頂点の次数の合計が常に $2|E|$ になる。各辺はその両端の頂点それぞれの次数に 1 ずつ寄与するためだ。

パスと閉路

頂点 $s$ から頂点 $t$ へのパス（path）とは、頂点の列

s = v_0,\; v_1,\; v_2,\; \ldots,\; v_k = t

で、隣接する各ペア $(v_i, v_{i+1})$ が $E$ の辺になっているものだ。パスの長さは $k$ — 通過する辺の数だ。

閉路（cycle）は同じ頂点から始まり同じ頂点で終わるパスで、少なくとも 1 本の辺を使う。閉路のないグラフを非巡回（acyclic）という。

A から D へのパス：  A → B → D    （長さ 2）
閉路：               A → B → D → C → A    （長さ 4）

閉路が重要なのは、非巡回グラフでは正しく動くアルゴリズムが閉路の存在で失敗したり誤った答えを出したりすることがあるためだ。

連結性

無向グラフはすべての頂点ペアの間にパスが存在するとき連結（connected）という — どの頂点からでも他のすべての頂点に到達できる。一部の頂点が他から到達不能な場合、グラフは非連結（disconnected）だ。極大な連結部分グラフを連結成分（connected component）という。

有向グラフでは連結性が 2 種類に分かれる：

強連結（strongly connected）：すべての頂点ペア $u$ , $v$ について $u$ から $v$ への有向パスと $v$ から $u$ への有向パスの両方が存在する。
弱連結（weakly connected）：辺の向きを無視した無向グラフが連結。

木

木（tree）は連結・無向・非巡回のグラフだ。以下の特徴付けはすべて同じものを表す：

$n$ 頂点の木は辺をちょうど $n - 1$ 本持つ。
任意の 2 頂点の間に単純パスがちょうど 1 本存在する。
辺を 1 本追加すると閉路ができ、1 本除くと非連結になる。

すでに知っている連結リストは退化した木 — すべての非葉が子を 1 つしか持たないパスグラフだ。木はコンピュータサイエンスのあらゆる場所に登場する：ファイルシステム、構文木（parse tree）、二分探索木、ヒープ。

DAG

有向非巡回グラフ（Directed Acyclic Graph / DAG）は有向閉路を持たない有向グラフだ。辺を辿ると常に「前方」に進み、一度訪れた頂点には戻れない。

DAG は依存関係を表すのに最適な構造だ：ビルドシステム（このファイルをリンク前にコンパイルする）、スプレッドシートの数式（参照元のセルより前にこのセルを評価する）、コースの前提条件（次のトピックの前にこのトピックを終える）。このサイト自体のチェックポイントグラフも DAG だ — 各チェックポイントが前提条件を宣言し、ビルドが閉路なしを検証する。

compile_a ──►
compile_b ──► link ──► package
compile_c ──►

DAG には閉路がないため、常にトポロジカル順序（topological order）を求められる。これはすべての辺が前の頂点から後の頂点を向くような頂点の線形な並べ方だ。この順序こそビルドシステムが何を最初にコンパイルするかを決める方法だ。

グラフのメモリ表現

グラフが何であるかを知ることと、グラフをどう格納するかは別の問いだ。2 つの標準的な表現 — 隣接行列（adjacency matrix）と隣接リスト（adjacency list）— は同じグラフを異なる形で格納し、空間と一般的な操作速度のトレードオフが逆転する。Zig でグラフを表現するでは完全な Zig 実装を交えて両方を解説している。

まとめ

グラフ $G = (V, E)$ は頂点の集合と頂点のペアを結ぶ辺の集合からなる。
無向グラフは辺が対称、有向グラフ（有向グラフ）は各辺に向きがある。
重み付きグラフは各辺に数値の重みを付与し、重み無しグラフは全辺を等しく扱う。
次数は頂点に接続する辺の数（有向グラフでは入次数と出次数に分かれる）。
パスは辺でつながれた頂点の列、閉路は出発点に戻るパス。
連結グラフはすべての頂点ペアの間にパスが存在する。
木は連結・非巡回・無向グラフで辺をちょうど $|V| - 1$ 本持つ。
DAG（有向非巡回グラフ）は有向閉路を持たず、常にトポロジカル順序を持つ — 依存関係の自然な表現形式だ。