データ構造とアルゴリズム
辺に向きのないグラフで、各頂点の隣の頂点が次のとおりである。A: B, C / B: A, D, E / C: A, F / D: B / E: B, F / F: C, E。頂点 A から再帰的な深さ優先探索を行う。隣の頂点はここに書いた順に調べ、まだ訪れていない頂点が見つかったらすぐにその頂点へ進む。頂点を訪れる順はどれか。
- AA, B, C, D, E, F
- BA, B, D, E, C, F
- CA, B, D, E, F, C
答えと解説を見る
正解：C. A, B, D, E, F, C
A から B へ進み、B の隣で最初の未訪問の D へ進みます。D の隣は訪問済みの B だけなので B に戻って次の E へ進み、E から未訪問の F へ、F からその隣の C へと進みます。したがって A, B, D, E, F, C の順です。A, B, C, D, E, F は、出発点から近い順に訪れる幅優先探索の順です。A, B, D, E, C, F は、E から未訪問の F へ進まずに戻ってしまっており、深さ優先探索の順にはなりません。
- A. 出発点から近い順に訪れる、幅優先探索の順です。
- B. E の隣に未訪問の F があるので、C に戻る前に F へ進みます。
- C. 正しい。行けるところまで進み、行き止まりになったら戻る順になっています。