データ構造とアルゴリズム
頂点が100万個、辺が300万本ほどの道路網のように、頂点の数に比べて辺の少ない(疎な)グラフをメモリに記憶する方法として適切なものはどれか。
- A隣接行列。2つの頂点の間に辺があるかを O(1) で調べられ、記憶領域も最も少なく済む
- B隣接リスト。記憶領域は頂点の数と辺の数の和に比例し、ある頂点から出る辺を順にたどるのに向いている
- C隣接行列。記憶領域は辺の数だけに比例する
答えと解説を見る
正解：B. 隣接リスト。記憶領域は頂点の数と辺の数の和に比例し、ある頂点から出る辺を順にたどるのに向いている
隣接行列は頂点数 V に対して V×V の表を使うので、100万頂点では10¹²個の要素が必要で、1要素1ビットでも約125 GBになります。隣接リストは各頂点につながる頂点だけを並べるので、記憶領域は O(V + E) で、この例なら数百万件程度で済みます。隣接行列は辺の有無を O(1) で調べられる利点があり、辺の多い(密な)グラフや頂点の少ないグラフに向いています。幅優先探索やダイクストラ法のように、頂点から出る辺を順にたどる処理では、隣接リストの方が効率よく動きます。
- A. 辺の有無を O(1) で調べられるのは正しいですが、記憶領域は頂点数の2乗に比例し、疎なグラフでは大きな無駄になります。
- B. 正しい。記憶領域が O(V + E) で済み、隣の頂点を順にたどる処理にも向いています。
- C. 隣接行列の大きさは辺の数によらず、頂点数の2乗になります。