頂点が ｎ 個で辺が ｍ 本のグラフ構造の問題を解くためのデータ構造として、隣接行列と隣接リストについての次の説明のうち、最も適切なものを選べ。
① 隣接行列を用いると、どのような問題に対しても時間計算量にＯ(1)で影響する。
② 隣接リストを用いると、領域計算量にＯ(ｎ)、時間計算量にＯ(ｎｍ)で影響する。
③ 有向グラフでは、隣接行列の方が適している。
④ 多くのアルゴリズムでは、疎なグラフでも隣接行列を用いても実用上の問題がない。
⑤ 密なグラフに、隣接リストを用いるのは、時間計算量、領域計算量ともに不利な場合が多い。
⑤
隣接行列は、頂点と頂点を結ぶ辺 (枝) の数を行列形式で表したものである。三角形の場合は以下のとおり
┌─┬─┬─┐
│①│②│③│
┌─┼─┼─┼─┤
│①│０│１│１│
├─┼─┼─┼─┤
│②│１│０│１│
├─┼─┼─┼─┤
│③│１│１│０│
└─┴─┴─┴─┘
また、四角形
①─②
│ │
④─③
の場合は、以下のとおり。
┌─┬─┬─┬─┐
│①│②│③│④│
┌─┼─┼─┼─┼─┤
│①│０│１│０│１｜
├─┼─┼─┼─┼─┤
│②│１│０│１│０｜
├─┼─┼─┼─┼─┤
│③│０│１│０│１│
├─┼─┼─┼─┼─┤
│④│１│０│１│０│
└─┴─┴─┴─┴─┘
① 2点間の隣接チェックの時間計算量はＯ(1)であるが、任意の点からの隣接チェックの時間計算量はＯ(n)である。
② 領域計算量はＯ(n+m)である。
③ 隣接行列に有向グラフのような向きは含めない。
④ 疎なグラフでは、無駄な計算が多くなる傾向にある。
⑤ 正しい。隣接リストは上記の四角形の場合、以下のとおり。
① → (①,②)、(①,④)
② → (②,①)、(②,③)
③ → (③,②)、(③,④)
④ → (④,③)、(④,①)
密なグラフでは、時間計算量、領域計算量ともに多くなり、不利と言える。
| Ⅳ－６ | 目次 | Ⅳ－８ |