【データ構造】木とは？隣接行列、隣接リストについて

はじめに

paizaで隣接行列に関する問題　と隣接リストに関する問題が出てきたので気になって調べました。

まずは、木を学んだあとに隣接行列、隣接リストについて解説します。

木とは？

木（Tree）は、以下の性質を持つグラフ構造です：

1. 連結性:
   • すべての頂点が連結しており、任意の2つの頂点間に経路が存在します。
2. サイクルがない:
   • 辺の数が $N - 1$ （頂点数 - 1）であり、閉路（サイクル）が存在しません。

基本的な用語

• ルート木（根付き木）: 特定の頂点を根（ルート）とした木。
• 子と親: 各頂点が他の頂点の親または子として関係します。
• 高さ: 木のルートから最も遠い頂点までの深さ。
• 葉（リーフ）: 子を持たない頂点。

隣接行列とは？

隣接行列（Adjacency Matrix）は、頂点間の接続を2次元配列（行列）で表現する方法です。

• 構造:
  $N \times N$ の行列 $g[i][j]$ によって、頂点 $i$ と $j$ の関係を表します。

  • $g[i][j] = 1$: 頂点 $i$ と $j$ が接続されている。
  • $g[i][j] = 0$: 頂点 $i$ と $j$ が接続されていない。

• 例（無向グラフの場合（グラフには有向グラフと無向グラフがあります））:
  頂点 1, 2, 3 が以下のように接続されているとします：

  1 - 2
  |
  3
  

  隣接行列:

  0 1 1
  1 0 0
  1 0 0
  

• 利点:

  • 接続確認（頂点 $i$ と $j$ が繋がっているか）を $O(1)$ で行える。

• 欠点:

  • スペース効率が悪い（辺の数が少ない疎グラフの場合に特に）。

隣接リストとは？

隣接リスト（Adjacency List）は、頂点ごとに接続先のリストを保持するデータ構造です。

• 構造:
  頂点 $i$ の隣接する頂点をリストで表します。

• 例（上記のグラフと同じ）:

  1: [2, 3]
  2: [1]
  3: [1]
  

• 利点:

  • スペース効率が良い（辺の数が少ない疎グラフで特に効果的）。

• 欠点:

  • 接続確認に $O(\text{隣接頂点の数})$ かかる。

隣接行列と隣接リストの比較

特徴	隣接行列	隣接リスト
構造	2次元配列	配列＋リスト
スペース効率	$O(N^2)$	$O(N + E)$
辺の存在確認	$O(1)$	$O(\text{隣接頂点数})$
辺の列挙	$O(N)$	$O(\text{隣接頂点数})$
疎グラフへの適用	不向き	向いている
実装の手軽さ	比較的簡単	やや複雑

おすすめ・参考書籍

問題解決力を鍛える！アルゴリズムとデータ構造 (ＫＳ情報科学専門書)
https://amzn.to/3YFmdH5