HOME»応用情報技術者平成29年秋期»午前問6
応用情報技術者平成29年秋期 午前問6
問6
ノード1～5をもつグラフを隣接行列で表したもののうち，木となるものはどれか。ここで，隣接行列のi行j列目の成分は，ノードiとノードjを結ぶエッジがある場合は1，ない場合は0とする。
分類
テクノロジ系 » アルゴリズムとプログラミング » データ構造
正解
イ
解説
各隣接行列からノード間のエッジを抽出し、図を描いて木構造になっているものを導きます。木構造とは1つの根と複数の節点および節点(根を含む)同士を結ぶ辺で構成され、ループをもたないデータ構造です。
- ノード間のエッジは"1－2","1－5","2－3","3－4","4－5"の5つです。全体がループになっているので木ではありません。
- ノード間のエッジは"1－2","1－5","2－3","2－4"の4つです。ループが存在しないため木構造になっています。よって、これが正解です。
- ノード間のエッジは"1－2","1－4","2－3","3－4","3－5"の5つです。1-2-3-4間がループ構造になっているので木ではありません。
- ノード間のエッジは"1－2","1－3","2－3","3－4","3－5","4－5"の6つです。1-2-3間および3-4-5間がループ構造になっているので木ではありません。
