1
アルゴリズムとデータ
構造
第１0回演習解答
2015/12/16
アルゴリズムとデータ構造 2016
第１0回演習解答1/2
2
[問]右図の無向グラフGについて答えよ．
1.グラフGの隣接行列と隣接リストを示せ．
隣接行列
é
ê
ê
ê
ê
ê
ê
ê
ê
ë
0
1
1
1
0
0
0
2015/12/16
1
0
1
0
1
0
0
1
1
0
1
1
1
0
1
0
1
0
0
1
0
0
1
1
0
0
1
1
0
0
1
1
1
0
1
0
0
0
0
1
1
0
ù
ú
ú
ú
ú
ú
ú
ú
ú
û
1
2
3
4
5
6
7
2
1
1
1
2
3
5
3
3
2
3
3
4
6
4
5
4
6
6
5
5
6
7
7
アルゴリズムとデータ構造 2016
第１0回演習解答1/2
3
[問]2.グラフGに対して頂点1 から深さ優先探索及び幅優
先探索を行ったとき，各頂点を最初に訪問するときに直前
に経由した辺からなる全域木をそれぞれ描け．ただし，複
数の辺が出ている頂点では，次に訪問する頂点は番号の
小さいものを優先するものとする．
深さ優先探索
2015/12/16
幅優先探索
アルゴリズムとデータ構造 2016

み ん な の 学 習 講 座

pptx