授業で示した深さ優先探索を実行するプログラムを改良して、探索頂点表示毎に、あわせて最初の頂点から当該頂点までに至る経路のエッジ数（段数）を表示せよ。
開始頂点の段数は０となる。
授業でのプログラムと同じく、ある頂点において経路に複数の選択肢がある場合は、頂点番号の小さい方を優先すること。
提出するプログラムとその実行結果については、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, 1, 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, 1, 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}};
|
| 【状況】 | 【指示】 |
| 誰かに教えてもらった場合： | その学生（氏名と９桁の学籍番号）をプログラム先頭に記し、さらにプログラム中コメントを使って、教えてもらったところの解説を数行以上書き込むこと。
（教えてもらった部分の解説コメントのないプログラムは全く評価しません。「全体です」のようなコメントの場合も同じです。） |
| 誰かに教えてあげた場合： | その学生（氏名・学籍番号）をプログラム先頭に記すこと。 |
| お互いに相談した場合： | お互いの氏名・学籍番号を、教えてもらった・教えてあげたの例に準拠して提出してください。 |
深さ優先探索のアルゴリズムを、必要十分な日本語を用いて説明せよ。
必要であれば図を挿入してもよい。
授業で提示した深さ優先探索のプログラムは、時間計算量、空間計算量とも O( N2 ) である。
この計算量を改善する方法を、プログラム上での改良すべき箇所を、示しながら説明せよ。
改良後の計算量も示せ。
必要ならグラフ中の辺数 M を表現に用いてよいが、その場合は 頂点数 N との関係を説明に含めること。
時間計算量、空間計算量、それぞれについて回答すること。
授業で提示した深さ優先探索のプログラムについて、探索中に経由する辺の数を数え上げて、新頂点に到達するたびにその辺数を同時に表示するようにプログラムを改良せよ。
また、プログラム終了時に、終了時までに経由した総経由辺数を表示するように改良せよ。
この総経由辺数は、実は実行前に予測をすることができる。その予測式とその根拠を説明せよ。