グラフの表現

グラフ表現は頂点と辺を保存・検索できるデータに変えます。隣接リストは頂点ごとに隣接点の行を持ち、空間は O(V + E)。隣接行列は V × V のマスを確保し、O(V²) の空間を使う代わりに、has_edge(u, v) を一回の添字参照で答えます。

リストは連絡先一覧のように、u を開けば実際の隣接点だけが並びます。行列は辺のない組も含め、全頂点対の場所を確保します。空間を使って固定位置の検索を得ます。

空間と検索速度の交換

このレッスンは単純無向グラフを使います。多重辺と自己ループはありません。辺 u-v に向きがないため、両表現とも対称に保存します。

リストでは adj[u] に v、adj[v] に u を追加します。無向辺 E 本は 2E 個の隣接項目となり、ほかに V 個の行入口を持ちます。

行列では matrix[u][v] = 1 と matrix[v][u] = 1 を書きます。主対角線に対して対称な二マスです。0 は辺なしを表し、自己ループがないので対角線は 0 のままです。

対称性が不変条件です。リストが両方向、行列が片方だけなら異なるグラフになります。リストも片方向だけなら有向の関係に変わります。

リストの次数は len(adj[u]) で分かりますが、辺の存在は行内で v を探します。行列は matrix[u][v] 一マスで辺を調べ、次数には行全体の合計が必要です。

表現をステップで追う

既定は頂点 0 から 5、辺は 0-1、0-2、1-3、2-3、3-4 の順です。5 は孤立していますが保存する行は必要です。

1. 空のリスト行を六つ、0 の 6 × 6 行列を作る。
2. 0-1：adj[0] に 1、adj[1] に 0 を追加。行列の [0][1] と [1][0] を 1 にする。
3. 0-2：adj[0] と adj[2] に対応する隣接点を追加し、[0][2] と [2][0] を 1 にする。
4. 1-3、2-3、3-4 にも同じ両方向の書き込みを行う。5 の隣接点は書かない。
5. 完成形は 0:[1,2]、1:[0,3]、2:[0,3]、3:[1,2,4]、4:[3]、5:[]。隣接項目は 2E = 10 個。
6. 行列は V² = 6² = 36 マス。頂点 3 の行は [0,1,1,0,1,0] で、隣接点 1、2、4 に対応する。
7. degree(3)：リストは len(adj[3]) = 3。行列は六マスを足して同じ 3 を得る。
8. has_edge(3, 5)：リストは 1、2、4 を順に 5 と比較し、三回で行末に達して False。
9. 行列は matrix[3][5] = 0 を一回読み、同じ False を返す。

画面では元の辺とともに、リストの二項目と行列の対称なマスを点灯します。検索時、リストのカーソルは一項目ずつ進み、行列のガイドは一マスで交差します。移動が検索費用を示します。

時間・空間計算量

V は頂点数、E は無向辺数、degree(u) は u の隣接点数です。

追加の費用は有効で重複のない入力に対する値で、別途の重複検査は含みません。任意の頂点対を何度も調べるなら行列、実在する隣接点を主にたどるならリストが候補です。

疎グラフでは E が V² より小さく、既定例は行入口六つと隣接項目十個に対して、行列は 36 マスを確保します。

Dense K5 は密な例です。五頂点十辺で、リストの論理項目数 V + 2E = 5 + 20 = 25 と行列の V² = 25 が一致します。これはバイト数の比較ではありません。各オブジェクトや参照の費用は異なります。ただし E = Θ(V²) ではリストの漸近的な空間優位が消えると分かります。

境界ケース

• 一頂点：空のリスト行と 0 の 1 × 1 行列。degree(0) = 0。
• 孤立頂点：既定の 5 は隣接点がなくても両表現に行を持つ。
• 存在しない辺：has_edge(3, 5) の False は通常の結果。
• 密なグラフ：Dense K5 ではリストの後方のヒットに四隣接点を走査し、疎な空間優位もなくなる。
• 自己ループ・多重辺：対象外。対応するなら対角要素と重複項目の規則が必要。

よくある間違い

• リストの片方向だけを書く。 無向辺なら adj[u] と adj[v] を更新します。
• 行列の一マスだけを書く。 [u][v] と [v][u] は一致させます。
• 行列の空間を O(E) とする。 0 が多くても V² マスを確保します。
• リストの辺検索を全グラフの走査とする。 調べるのは adj[u] だけで、O(degree(u)) です。
• 論理項目数をバイト数とする。 V + 2E と V² は増え方を示し、一項目のメモリ量が同じとは述べていません。