1 隣接リストの概要
1.1 定義と基本概念
1.1.1 隣接先の保持方法
隣接リスト（adjacency list）は、グラフを「各頂点から直接到達できる頂点の集合」として保持する表現形式である。具体的には、頂点ごとに参照できる近傍（隣接先）の列または集合を持ち、頂点 \(v\) に対する隣接リストには、\(v\) から1ステップで到達可能な頂点が格納される。
この方式では、グラフのエッジが少ない（疎）場合に特に都合がよい。隣接行列のように全頂点ペア分の領域を確保せず、現実に存在する接続関係に比例した量の情報を保持するためである。
1.1.2 有向グラフ・無向グラフでの違い
有向グラフでは、エッジが「出発点から到達点への向き」を持つため、隣接リストは出辺（outgoing）を列挙する形が基本となる。つまり、頂点 \(u\) の隣接リストには、\(u \rightarrow v\) のような向きのある接続先 \(v\) が入る。
一方、無向グラフではエッジに向きがないため、接続関係は両方向に意味を持つ。したがって、エッジ \(\{u,v\}\) は通常、\(u\) の隣接リストにも \(v\) の隣接リストにも同時に記録される。これにより探索時に「相互にたどれる」性質を自然に反映できる。
1.2 表現対象となるグラフの種類
1.2.1 非重みグラフ
非重みグラフでは、隣接リストの各要素は主に隣接先の頂点識別子（ラベル、番号など）で構成される。エッジのコストや容量といった追加情報が不要な場合、隣接先だけを保持すればよい。
この場合、探索アルゴリズムは「次に行ける頂点集合」を得る操作を隣接リストの走査で実現できる。結果として、探索の記述が簡潔になり、実行時の参照も規則的になる。
1.2.2 重み付きグラフ
重み付きグラフでは、エッジに数値属性（重み）を付与する。隣接リストは通常、隣接先に加えて、その辺の重みを保持する拡張形式になる。たとえば、隣接リストの各要素を「(隣接先, 重み)」のペアとして表す。
重みの保持により、経路探索で必要となる評価（累積コスト、優先度など）をその場で更新できる。単に到達可能性を調べる用途よりも、演算を含む処理が増えるため、データの詰め方や型の設計が性能に影響しやすい。
1.2.3 マルチグラフと自己ループ
マルチグラフは、同一の頂点対の間に複数のエッジが存在し得る。隣接リストでは、同じ隣接先が複数回現れる、あるいは各エッジの識別や重みの違いを要素として区別する形で表現する。重複をどう扱うかは後段のアルゴリズム次第であり、「重複エッジをそのまま保持する」設計か「統合して代表値にする」設計かを決める必要がある。
自己ループは、頂点 \(v\) に対して \(v\) へ戻るエッジが存在する状態である。隣接リストでは、頂点 \(v\) の隣接先として \(v\) 自身が含まれることで表せる。探索・経路探索では、訪問管理や距離更新の条件により、自己ループが処理結果へ与える影響が変わる。
2 隣接リストの作成方法
2.1 行列表現からの変換
2.1.1 隣接行列からの生成手順
隣接行列 \(A\) から隣接リストへ変換するには、行（または列）の走査により「接続がある頂点」を抽出する。無向グラフであれば対称性を利用して重複を避ける工夫ができるが、基本は各セルを調べて、非ゼロ（または真）となる位置に対応する頂点を隣接先として追加する。
非重みの場合、行列の値が 0/1 のような単純な表現であれば、1 の位置に対応する列番号（頂点番号）をリストへ追加する。重み付きでは、セルの値を重みとして併せて保持する。
有向では、行 \(u\) を見て \(A[u][v]\) が存在を示すなら \(u\) の隣接リストに \(v\) を追加する。無向では、通常 \(A[u][v]\) が非ゼロなら両方向を意味するため、変換時に両方へ追加するか、片側だけ処理して対称分を補う。
2.1.2 変換時の計算量
隣接行列は頂点数 \(n\) に対して \(n^2\) 規模の情報を持つため、素朴な変換は概ね \(O(n^2)\) の走査が必要になる。疎なグラフであっても、行列としては「存在しないエッジの領域」まで確認するため、入力が巨大な場合は変換コストが支配的になり得る。
一方、隣接リストは実際のエッジ数 \(m\) に比例するため、変換後の探索は \(O(n+m)\) 程度の典型的な挙動に収まることが多い。したがって、変換は「データの作り方」だけでなく、「後でどれだけ使うか」という前提とセットで評価するのが実務的である。
2.2 エッジ入力からの直接構築
2.2.1 有向エッジの追加
有向グラフとしてエッジが列挙されて入力される場合、各エッジ \((u,v)\) について、頂点 \(u\) の隣接リストに \(v\)（および重みがあるなら重みも）を追加する。これにより、出辺をそのまま表現できる。
構築時は、頂点数が事前に分かっているなら隣接リストの外側配列（頂点数ぶん）を確保してから、各エッジを投入するのが一般的である。頂点数が不明なら、最大値の推定や到達点の追加に伴う伸長設計が必要になる。
2.2.2 無向エッジの追加
無向グラフでは、入力エッジ \(\{u,v\}\) を受け取ったら、\(u\) の隣接リストへ \(v\)、\(v\) の隣接リストへ \(u\) をそれぞれ追加する。重み付きなら両方に同じ重み（あるいは表現方針に応じた値）を格納する。
このとき、自己ループ \(\{v,v\}\) が入力に含まれる可能性がある。実装では、自己ループを二重に追加してしまわないよう、追加処理を条件分岐で調整することがある。どのように扱うかは、後段のアルゴリズムが自己ループをどう解釈するかに合わせる。
2.3 動的更新への対応
2.3.1 頂点追加
頂点を後から追加する場合、隣接リストの外側構造に新しい要素（空の隣接先リスト）を作成して追加する。頂点番号を連番で管理しているなら、最後に次の番号を付けるだけでよい。
頂点番号の割り当て方針によっては、既存の参照を壊さないよう、内部の識別子管理層（マッピング）を用意する設計が取り入れられる。特にハッシュを介して外部IDと内部IDを対応付ける方式では、更新時の一貫性を重視する必要がある。
2.3.2 エッジ追加・削除
エッジ追加は、対象の出発点の隣接先リストへ要素を追記するだけで済むことが多い。ただし、重複エッジを許すか許さないかにより、追加前に既存の有無を調べる必要がある。
削除はより工夫が要る。隣接先を配列（可変長配列、リスト）で保持している場合、削除対象の要素を見つけてから除去する操作が必要になり、位置によっては線形時間を要する。集合構造（ハッシュ集合など）で保持していれば、存在判定と削除が効率化される場合があるが、順序の概念が失われるなど別のトレードオフが生じる。
3 アルゴリズムとの関係
3.1 グラフ探索
3.1.1 深さ優先探索（ＤＦＳ）
深さ優先探索（DFS）は、隣接先を逐次的にたどりながら、未訪問の頂点を可能な限り深く探索する。隣接リストでは、ある頂点 \(u\) を取り出したときに \(u\) の隣接先リストを走査し、その中の未訪問頂点へ再帰またはスタック操作で進む。
隣接リストの利点は、「実際に存在する近傍だけを列挙できる」点にある。隣接行列のように無関係な頂点を大量にスキップする必要がないため、探索のボトルネックが必要な情報の取得に近づく。
3.1.2 幅優先探索（ＢＦＳ）
幅優先探索（BFS）は、探索を層（距離の増加に相当）ごとに進める。隣接リストでは、キューから頂点 \(u\) を取り出し、隣接先リストを順に調べて未訪問の頂点をキューへ追加する。
BFSが効率的に動く理由は、隣接先の列挙がエッジ数に比例するためである。訪問管理（訪問済みフラグや距離配列）と組み合わせることで、同一頂点の重複処理を避け、探索全体を \(O(n+m)\) の範囲に収めやすい。
3.2 経路探索・最短経路
3.2.1 重み付きでの方針（概要）
重み付きグラフでの最短経路問題では、代表的な方針として、非負重み条件下でのアルゴリズム（例：ダイクストラ法）や、負の重みを許す場合の別手法がある。隣接リストは、どのアルゴリズムでも「辺の取り出し」を効率化する役割を担う。
ダイクストラ法のように優先度付きの探索では、頂点を確定した後に、その頂点の隣接先へ候補距離を更新する。隣接リストがあることで、更新に必要な遷移先がその場で列挙でき、不要な頂点ペアを調べずに済む。重みを要素として保持している場合、更新計算に必要な値が同じ走査内で得られる。
3.2.2 使用するデータ構造との相性
最短経路の計算では、優先度付き待ち行列（ヒープなど）や距離配列、訪問済み判定など複数のデータ構造が関与する。隣接リストは、これらのうち特に「隣接辺の列挙」と相性がよい。
配列として隣接先を保持すれば、走査が連続領域になりやすくキャッシュ効率が良い場合がある。集合として保持すれば、重複排除や削除が容易になることがあるが、列挙順やメモリ局所性に影響が出ることがある。したがって、最短経路の更新回数と、隣接先の取り出し頻度を見積もり、保持形式を決めるのが実務上のポイントになる。
3.3 全体処理（連結成分など）
3.3.1 連結性の判定
連結性の判定では、グラフの性質に応じて DFS や BFS を行い、「到達可能な頂点の集合」が全頂点を覆うかどうかを調べる。隣接リストでは、到達可能性の拡張が隣接先走査として自然に実装できる。
無向グラフであれば単純な連結判定に加え、連結成分の列挙（未訪問頂点からの探索を繰り返す）も同様の枠組みで行える。有向グラフで同様の判定を行う場合は、到達性や強連結性など判定の定義に応じた探索計画が必要になる。
3.3.2 トポロジカルな処理（概説）
トポロジカルな処理は、前提となる有向非巡回性（DAG）などの条件がある場合に有効になる。隣接リストは、各頂点からの出辺を列挙して次の候補を更新する流れに適している。
例えば、DAG のトポロジカル順序付けでは、入次数（in-degree）の管理と、ある頂点の処理後にその隣接先の入次数を下げる操作が中心となる。隣接リストを使うことで「入次数を下げる対象の集合」が効率よく得られ、処理全体の見通しが立つ。
4 実装上の設計指針
4.1 計算量とメモリ効率
4.1.1 疎グラフでの利点
隣接リストは、エッジ数 \(m\) が頂点数 \(n\) に比べて小さいとき、メモリ使用量を抑えやすい。隣接行列は常に \(n^2\) 規模を確保するが、隣接リストは保持するのが「存在する接続のみ」になるためである。
探索・経路探索の計算量も、一般に \(O(n+m)\) の形で整理できることが多い。したがって、疎な領域では実行時間・メモリの両面で改善が見込まれる。
4.1.2 間接参照コストの考え方
一方で、隣接リストは「頂点ごとの別領域」への参照が発生しやすく、実行環境によっては間接参照が遅延要因になる。これはキャッシュ局所性の観点で説明できる。
設計では、隣接先を連続領域に近づける（たとえば配列でまとめて保持する）工夫や、頂点アクセスパターンを踏まえたデータ配置を検討する価値がある。理論上の計算量が同じでも、実装上のデータ配置で体感速度が変わり得る。
4.2 データ構造の選択
4.2.1 リスト・配列・集合の使い分け
隣接先の保持にリスト（連結リスト）を使うと、要素の挿入や削除は柔軟になり得るが、走査での局所性が弱くなりがちである。配列（動的配列）を使えば走査が速くなりやすいが、削除が高コストになり得る。
集合（ハッシュ集合など）を使うと、重複の抑制や存在確認が簡単になり、削除も扱いやすい場合がある。ただし、列挙順が安定しないことがあり、再現性のある出力が必要なケースでは工夫が要る。
4.2.2 重みや属性の保持形式
重み付きでは、隣接要素に対して追加フィールドを持たせる。典型的には「隣接先ID」と「重み」を一つの要素としてまとめる。属性が複数（容量、コスト種別、通行可否など）ある場合は、構造体や小さなレコード型として設計するのが一般的である。
更新頻度が高い属性と読み取り専用の属性を分ける、あるいは配列で分離するなどの工夫により、必要なデータだけを取り出す処理が可能になり、効率の改善につながることがある。
4.3 正しさと運用上の注意
4.3.1 重複エッジの扱い
隣接リストに同一の隣接先が複数回現れることは、マルチグラフとして自然に許される場合がある。一方で、アルゴリズムが「最小コストの辺のみを想定」しているなら、重複をそのまま保持すると更新が冗長になったり、距離更新条件によっては挙動が変わったりする可能性がある。
このため、入力段階で統合する（同一対の辺を代表値にまとめる）か、保持したままアルゴリズム側で考慮するかを決める必要がある。仕様として「重複を許す/許さない」「重みの取り扱い方針」を明文化することが望ましい。
4.3.2 頂点番号の管理方法（連番・ハッシュ等）
頂点識別子は、連番（0..n-1 のような範囲）で管理すると実装が単純になりやすい。配列をインデックスとして直接参照でき、距離配列や訪問フラグの扱いも容易である。
外部データの頂点IDが飛び飛びの場合は、ハッシュマップで内部番号へ変換する管理層を導入することがある。このとき、変換の一貫性（同じ外部IDは必ず同じ内部IDに写像される）と、更新時に新規IDが出現した場合の割り当て規則を決めることが重要になる。
4.3.3 並び順がアルゴリズムに与える影響
隣接先の並び順は、探索アルゴリズムの訪問順に影響し得る。DFS や BFS は一般に「どの探索木になるか」を隣接列挙順で変えるため、出力される経路や探索順のような非本質的な差が発生する可能性がある。
ただし最短距離の値そのものなど、順序に依存しない量は変わらないことが多い。検証やテストでは、順序非依存の性質を確認するのか、順序まで一致させる必要があるのかを事前に決め、隣接リストの作り方（挿入順、ソート有無）に反映させるとよい。