データ構造 (全29問中3問目)

No.3

ノード1〜5をもつグラフを隣接行列で表したもののうち,木となるものはどれか。ここで,隣接行列のi行j列目の成分は,ノードiとノードjを結ぶエッジがある場合は1,ない場合は0とする。

分類

テクノロジ系 » アルゴリズムとプログラミング » データ構造

正解

解説

各隣接行列からノード間のエッジを抽出し、図を描いて木構造になっているものを導きます。木構造とは1つの根と複数の節点および節点(根を含む)同士を結ぶ辺で構成され、ループをもたないデータ構造です。
  • ノード間のエッジは"1−2","1−5","2−3","3−4","4−5"の5つです。
    06aa.gif/image-size:339×168
    全体がループ構造になっているので木ではありません。
  • ノード間のエッジは"1−2","1−5","2−3","2−4"の4つです。
    06ii.gif/image-size:339×168
    "2"を根とした木構造になっているので、これが正解です。
  • ノード間のエッジは"1−2","1−4","2−3","3−4","3−5"の5つです。
    06uu.gif/image-size:339×168
    1-2-3-4間がループ構造になっているので木ではありません。
  • ノード間のエッジは"1−2","1−3","2−3","3−4","3−5","4−5"の6つです。
    06ee.gif/image-size:339×168
    1-2-3間および3-4-5間がループ構造になっているので木ではありません。
© 2010-2018 応用情報技術者試験ドットコム All Rights Reserved.

Pagetop