下図において、左側の木に対して矢印で指定したノードを根とすると右側に示したような根つき木になります。このとき、根を探索の始点となる頂点とするのが自然でしょう。順序によって変わることにも注意します)。まで猪突猛進に突き進み、行き止まりになったら一歩戻って新たな分岐を試している様子がわかります。頂点をすべて探索して...といった具合に、根に近いところからこまめに探索していることがわかります。(スタック)というデータを用いた実装を行いました。再帰関数と相性がよく、組込系でない限りは、しばしば再帰関数を用いて実装されます。章で見るような複雑な処理を行う段階になると、再帰関数を用いることで、非再帰な実装よりも簡潔に実装できることが多いです。実装のテンプレを下に示します。簡潔に書けることがわかります。配列についてはそのまま活用します。配列をグローバル変数としていますが、実際は再帰関数の引数とするか、クラスのメンバ変数とするなどの工夫を行うとよいでしょう。探索順序について掘り下げてみましょう。ついて学ぶときの理解の助けになります。(一般のグラフの場合も、深さ優先探索木を考えることで結局は木の場合と同様になりますが、ここでは省略します)。実は下図のようにグルッと一筆書きをするような動きをしています。木の場合の探索順」でも示したものですが、これは特に「根から初めて訪問した頂点の順序で順位をつけたもの」を意味していて行きがけ順といいます4。他の探索順として、下図のように「最後に訪問した頂点の順序で順位をつけたもの」を意味する帰りがけ順があります56。コード上ではどのように対応するのかを確認しておきましょう。再帰関数のメイン部分だけを取り出すと以下のようになります。順位ということになります。}}このことを実際に確かめてみましょう。グラフインスタンスとしては、上図に対応する以下のものを用います。(すなわち、再帰関数を用いて行きがけ順を求めたとき、その順位と頂点番号とは一致するはずです)。endl;}結果は以下のようになりました。行きがけ順はきちんと頂点番号と一致しており、帰りがけ順も正しく求められていることがわかります。