から




専門/H18/07

正解 Edit

5

選択肢の検証 Edit

  1. 隣接行列を用いると,どのような問題に対しても時間計算量にO(1)で影響する。
    • 特定のペア (u, v) が辺集合に含まれるかどうかの確認が O(1)
    • 各頂点に隣接する頂点をすべて数え上げるのに O(n) の時間がかかる
  2. 隣接リストを用いると,領域計算量にO(n),時間計算量にO(nm)で影響する。
  3. 有向グラフでは,隣接行列の方が適している。
    • 隣接リストの方が適している。
  4. 多くのアルゴリズムでは,疎なグラフでも隣接行列を用いても実用上の問題がない。
    • 疎なグラフは隣接リストを用いた方が良い。
  5. 密なグラフに,隣接リストを用いるのは,時間計算量,領域計算量ともに不利な場合が多い。
    • 正しい。
  • ソース「隣接リストと幅優先探索
    • 隣接行列では、特定のペア (u, v) が辺集合に含まれるかどうかの確認が O(1) の時間でできるが、O(n2) の記憶領域を必要とし、各頂点に隣接する頂点をすべて数え上げるのに O(n) の時間がかかる。このため辺の数 e が n2 よりもはるかに少ない疎なグラフに対しては無駄が多い。
    • そこで、疎なグラフに対しては通常隣接リスト と呼ばれるデータ構造が用いられる。これは簡単な話で、各頂点につながっている辺の集合を、リストの形で持っておく のである。これだとメモリが O(n + e) で済むし、辺の数え上げも次数のオーダーで済む。但し、特定の辺がグラフに含まれているかどうかを確かめるためにはリストを手繰らなければならない。

Tag: グラフ




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