授業で示したプログラムをベースに、１つのプログラムで深さ優先探索と幅優先探索を実行するプログラムを作成せよ。
・深さ優先探索で訪れる頂点を、訪れる順に表示すること(D)。
・幅優先探索で訪れる頂点を、訪れる順に表示すること(W)。
・上記の結果(D)(W)で、訪れる順が一致する頂点があれば、それを表示すること。
・授業でのプログラムと同じく、ある頂点において経路に複数の選択肢がある場合は、頂点番号の小さい方を優先すること。
・提出するプログラムとその実行結果については、MAP_Aだけでよい。
・変数名、ループ、条件分岐などでコメントを整備すること。
・出力結果が読みやすくなるように、テキスト出力部分を工夫してあればその分を高評価します。
| MAP_A |
#define N 10
int edge[N][N] = {
{0, 0, 0, 0, 0, 1, 0, 1, 0, 0},
{0, 0, 0, 1, 0, 0, 0, 1, 1, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 1},
{0, 1, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 1, 0, 0},
{1, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 1},
{1, 1, 0, 0, 1, 0, 0, 0, 0, 0},
{0, 1, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 1, 0, 0, 0, 1, 0, 0, 0}
};
|
| 【状況】 | 【指示】 |
| 誰かに教えてもらった場合： | その学生（氏名と９桁の学籍番号）をプログラム先頭に記し、さらにプログラム中コメントを使って、教えてもらったところの解説を独自の説明で数行以上書き込むこと。
（教えてもらった部分の解説コメントのないプログラムは全く評価しません。「全体です」のようなコメントの場合も同じです。） |
| 誰かに教えてあげた場合： | その学生（氏名・学籍番号）をプログラム先頭に記すこと。 |
| お互いに相談した場合： | お互いの氏名・学籍番号を、教えてもらった・教えてあげたの例に準拠して提出してください。 |
深さ優先探索のアルゴリズムを、必要十分な日本語を用いて書き下せ。
必要であれば図を挿入してもよい。
・深さ優先探索と幅優先探索でそれぞれ使われた処理の概念であるスタックとキューについて、図を用いて説明せよ。
・特に、なぜこの２つが概念として対を成すのか、類似点と相違点にわけて記述すること。
必修課題１Ａのプログラムについて、下記の内容を表示できるように改良を施せ。
・深さ優先で訪れる頂点を順に表示するとき、探索開始頂点からそれぞれの頂点に至る経路を頂点毎に示せ。
・幅優先で訪れる頂点を順に表示するとき、探索開始頂点から当該頂点にまでに経由する辺数を示せ。