分野別過去問題テクノロジ系　データ構造 No.13

データ構造(全39問中13問目)

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

出典：平成29年秋期　問 6

正解　イ問題へ

分野：テクノロジ系
中分類：アルゴリズムとプログラミング
小分類：データ構造

解説

各隣接行列からノード間のエッジを抽出し、図を描いて木構造になっているものを導きます。木構造とは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間がループ構造になっているので木ではありません。