グラフを計算機上で表現する代表的な方法として隣接行列と隣接リストが知られています.

隣接行列

グラフ$G=(V,E)$の隣接行列とは, 行列 $A\in \{0,1\}^{V\times V}$ であり, 各$(i,j)$成分 $A(i,j)$ は

\[A(i,j) = \begin{cases} 1 & \text{if $\{i,j\}\in E$},\\ 0 & \text{otherwise}. \end{cases}\]

で与えられるものである. 有向グラフの場合も同様に, $(i,j)$成分を有向辺$(i,j)$の有無で定める.

無向グラフの隣接行列は常に対称行列となりますが, 有向の場合は必ずしもそうとは限りません.

プログラムで書く時は二次元リストで表現し, A[i][j]に$A_{i,j}$ を格納します. 本講義では特に自己ループ $u\sim u$ となるグラフは考えないので常に $A_{i,i}=0$ となります.

例えば上図のグラフを隣接行列で表現すると以下の行列になります.

\[\begin{align*} A = \begin{bmatrix} 0 & 1 & 0 & 0 & 0 & 0\\ 1 & 0 & 1 & 1 & 0 & 0\\ 0 & 1 & 0 & 1 & 0 & 0\\ 0 & 1 & 1 & 0 & 1 & 0\\ 0 & 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 \end{bmatrix} \end{align*}\]

頂点5はどの頂点とも隣接していないため, 頂点5に対応する行と列の成分は全て$0$になっています.

隣接リスト

隣接リストNは二次元リストであり, $i=0,1,\dots,n-1$ に対して N[i]は長さ$\deg(i)$ のリストであり, $i$ と隣接している頂点を格納されています. ここで$\deg(i)$ は頂点 $i$ の次数です.

例えば上図のグラフを隣接リストで表現すると以下のリストになります:

  N = [
    [1],    #頂点0の隣接頂点のリスト
    [0,2,3],#頂点1に隣接頂点のリスト
    [1,3],
    [1,2],
    [3],
    []      #頂点5に隣接している頂点は存在しない
  ]

例えば N[0] は頂点$0$に隣接している頂点が格納されたリストになっています.

重み付きグラフの表現

重み付きグラフ$G=(V,E,w)$も隣接リストを少し修正するだけで表現できます. 隣接リストを wN とすると各 wN[u] は頂点$u$に隣接している頂点とその頂点に向かう辺の重みをタプルとして保持するリストとします.

例えば上図のグラフを重み付き隣接リストで表現すると

  wN = [
    [(2,16)],    #頂点0からは頂点2に向かう重さ16の辺が存在
    [(2,8),(3,11)],
    [(0,16),(1,8),(3,7)],
    [(1,11),(2,7)],
    [(3,9)],
    []
  ]

となります