概要
グラフを表現するためのデータ構造である隣接リストと隣接リストについてまとめる。
隣接リストや隣接行列は有向グラフでも無向グラフでも利用できる。
隣接リスト（Adjacency List）
各頂点（ノード）ごとに隣接する頂点をリストとして持つデータ構造。
計算量
空間計算量： O(V+E) ※Vは頂点数、Eは辺の数 特定の頂点の隣接する頂点を見つける： O(1) 特定の辺の存在を判定する: O(degree) ※degreeは隣接する辺の数 全ての頂点の隣接する頂点を列挙する: O(V+E)
隣接リストは辺の数が少ないグラフだと計算量が効率なデータ構造。
実装
ソースコードはadjacency_list。
辺（エッジ）を足す処理が複雑である。
隣接行列（Adjacency Matrix）
頂点（ノード）間の接続関係を2次元の行列として表現するデータ構造。
頂点間の辺（エッジ）の有無は0または1の値が使われる。
計算量
空間計算量: O(V^2) 特定の頂点の隣接する頂点を見つける： O(V) 特定の辺の存在を判定する: O(1) 全ての頂点の隣接する頂点を列挙する: O(V^2)
隣接行列は辺の数が多いグラフや辺の存在を頻繁に判定するような必要がある場合に効率的なデータ構造。
実装
ソースコードはadjacency_matrix。
辺（エッジ）を足す部分の条件が少しややこしいかもしれない。