平成18年度 技術士第一次試験問題【専門科目】
【16】情報工学部門
W−7
頂点が 個で辺が m 本のグラフ構造の問題を解くためのデータ構造
として、隣接行列と隣接リストについての次の説明のうち、最も適切なものを
選べ。

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



【正解】 D

隣接行列は、頂点と頂点を結ぶ辺 (枝) の数を行列形式で表したもので
ある。三角形の場合は以下のとおり
   ┌─┬─┬─┐
   │@│A│B│
 ┌─┼─┼─┼─┤
 │@│0│1│1│
 ├─┼─┼─┼─┤
 │A│1│0│1│
 ├─┼─┼─┼─┤
 │B│1│1│0│
 └─┴─┴─┴─┘
また、四角形
 @─A
 │ │
 C─B
の場合は、以下のとおり。
   ┌─┬─┬─┬─┐
   │@│A│B│C│
 ┌─┼─┼─┼─┼─┤
 │@│0│1│0│1|
 ├─┼─┼─┼─┼─┤
 │A│1│0│1│0|
 ├─┼─┼─┼─┼─┤
 │B│0│1│0│1│
 ├─┼─┼─┼─┼─┤
 │C│1│0│1│0│
 └─┴─┴─┴─┴─┘

@2点間の隣接チェックの時間計算量はO(1)であるが
 任意の点からの隣接チェックの時間計算量はO(n)である。
A領域計算量はO(n+m)である。
B隣接行列に有向グラフのような向きは含めない。
C疎なグラフでは、無駄な計算が多くなる傾向にある。
D正しい。隣接リストは上記の四角形の場合、以下のとおり。
 @→(@,A)→(@,C)
 A→(A,@)→(A,B)
 B→(B,A)→(B,C)
 C→(C,B)→(C,@)
密なグラフでは、時間計算量、領域計算量ともに多くなり、不利と言える。

EXCELのマクロのご相談なら ファーストマクロ 



W−6 目次 W−8
ファーストマクロ TOPページ