頂点1〜6と、辺 1−2, 1−3, 2−4, 2−5, 3−6, 5−6 からなる無向グラフがある。頂点1から深さ優先探索を行い、未訪問の隣接頂点が複数あるときは番号の小さい順に選ぶ。頂点を訪問する順序はどれか。

解説

正解は「1, 2, 4, 5, 6, 3」です。深さ優先探索は、未訪問の隣接頂点があれば先へ進み、行き止まりになったら戻って別の頂点を調べます。1から番号の小さい2へ進み、2から4へ進みます。4の先は行き止まりなので2に戻って5へ進み、5から6、6から3へ進みます。3の隣接頂点はすべて訪問済みなので、探索は終了します。「1, 2, 3, 4, 5, 6」は、始点に近い頂点から順に訪問する幅優先探索の結果です。「1, 3, 6, 5, 2, 4」は、番号の大きい順に選んだ場合の深さ優先探索の結果です。「1, 2, 4, 5, 3, 6」は、5から隣接する6へ進まずに3を訪問しており、規則に反しています。