グラフにおける隣接リストの表現方法

グラフにおける隣接リストの表現方法についてまとめたいと思います。
まずは、隣接リストの定義についてまとめます。(AIZU ONLINE JUDGEから引用)

隣接リストとは

隣接リスト表現では、V の各頂点に対して１個、合計 |V| 個のリスト Adj[|V|] でグラフを表します。
頂点 u に対して、隣接リスト Adj[u] は E に属する辺 (u,vi) におけるすべての頂点 vi を含んでいます。
つまり、Adj[u] は G において u と隣接するすべての頂点からなります。

この表現方法だと一目で理解するのは、難しいですが、
隣接リストの入力方法を見れば、理解しやすいです。
隣接リストの入力方法では、以下のような形で与えられます。

隣接リストの入力方法

最初の行に G の頂点数 n が与えられます。
続く n 行で各頂点 u の隣接リスト Adj[u] が以下の形式で与えられます：

u k v1 v2 ... vk

u は頂点の番号、k は u の出次数、v1v2...vk　は u に隣接する頂点の番号を示します。

つまり、隣接リストとして以下のような形で入力されます。

1 2 2 4

これは頂点1に2個隣接している頂点があり、それが2と4であることを示しています。

この形式を表現するには、vectorが適しています。

隣接リストをvectorで表現する

以下のようにvectorの領域を頂点分用意することによって、
隣接行列を簡単に表現することができます。

// 頂点分vectorの領域を用意する
vectorgraph[n];
// 頂点uに隣接するvを追加する
graph[u].push_back(v);

// 頂点uに隣接する頂点を探索する場合
for(int i = 0;i < graph[u].size;++i){
 // 隣接する頂点を取得する
 int v = graph[u][i];
} 

隣接リストを用いた計算量

隣接リストを用いて、幅優先探索・深さ優先探索は、
各頂点を一度訪問して、隣接リストの頂点を調べるので、
O(|V| + |E|)の計算量になります。