から




IV-7 Edit

頂点がn個で辺がm本のグラフ構造の問題を解くためのデータ構造として,隣接行列と隣接リストについての次の説明のうち,最も適切なものを選べ。

  1. 隣接行列を用いると,どのような問題に対しても時間計算量にO(1)で影響する。
  2. 隣接リストを用いると,領域計算量にO(n),時間計算量にO(nm)で影響する。
  3. 有向グラフでは,隣接行列の方が適している。
  4. 多くのアルゴリズムでは,疎なグラフでも隣接行列を用いても実用上の問題がない。
  5. 密なグラフに,隣接リストを用いるのは,時間計算量,領域計算量ともに不利な場合が多い。

memo Edit

Link Edit


Tag: グラフ



トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 下位頁新規  一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2010-02-22 Mon 23:18:59 JST (3016d)