組合せとグラフの理論（塩田）第6回 (4) 深さ優先探索
アルゴリズム
次は深さを優先します。例題
Ex.16 再び二分木でチョー丁寧に動作を確認しましょう。
次の図で $v=0$ を根として深さ優先探索を実行します。 最初は、スタック $S$ は空、赤い部分が $T$ です。
探索点（青い頂点）は $x=0$とします。
$x=0$ の隣接点 $1$, $2$ のうち番号の小さい方を $y=1$ とします。
$S$ の先頭に $x=0$ を追加し $S=\{\,0\,\}$,
$T$ には辺 $01$ を付加し、探索点を $x=1$ とします。
$x=1$ の未探索な隣接点 $3$, $4$ のうち番号の小さい方を $y=3$ とします。
$S$ の先頭に $x=1$ を追加し $S=\{\,1,0\,\}$,
$T$ には辺 $13$ を付加し、探索点を $x=3$ とします。
$x=3$ には未探索な隣接点はありませんので、
$S$ の先頭から $x=1$ を取り出し探索点とします。$S=\{\,0\,\}$ になります。
$x=1$ の未探索な隣接点は $4$ のみですので $y=4$ とします。
$S$ の先頭に $x=1$ を追加し $S=\{\,1,0\,\}$,
$T$ には辺 $14$ を付加し、探索点を $x=4$ とします。
$x=4$ には未探索な隣接点はありませんので、
$S$ の先頭から $x=1$ を取り出し探索点とします。$S=\{\,0\,\}$ になります。
$x=1$ には未探索な隣接点はありませんので、
$S$ の先頭から $x=0$ を取り出し探索点とします。$S=\{\ \}$ になります。
$x=0$ の未探索な隣接点は $2$ のみですので $y=2$ とします。
$S$ の先頭に $x=0$ を追加し $S=\{\,0\,\}$,
$T$ には辺 $02$ を付加し、探索点を $x=2$ とします。
$x=2$ の未探索な隣接点 $5$, $6$ のうち番号の小さい方を $y=5$ とします。
$S$ の先頭に $x=2$ を追加し $S=\{\,2,0\,\}$,
$T$ には辺 $25$ を付加し、探索点を $x=5$ とします。
$x=5$ には未探索な隣接点はありませんので、
$S$ の先頭から $x=2$ を取り出し探索点とします。$S=\{\,0\,\}$ になります。
$x=2$ の未探索な隣接点は $6$ のみですので、$y=6$ とします。
$S$ の先頭に $x=2$ を追加し $S=\{\,2,0\,\}$,
$T$ には辺 $26$ を付加し、探索点を $x=6$ とします。
未探索点が無くなりましたので人間がやるときはここでおしまいです。
（アルゴリズム的にはこのあと、$2$, $0$ を $S$ から取り出して $S$ が空になって終了します。）
次の図で $v=0$ を根として深さ優先探索を実行します。 最初は、スタック $S$ は空、赤い部分が $T$ です。
Ex.18 Ex.14と同じグラフで、やはり $v=0$ を根として、ラフにやってみます。
根 $0$ から一番番号の小さい未探索点 $1$ へ進みます。
探索点 $1$ から一番番号の小さい未探索点 $2$ へ進みます。
探索点 $2$ から一番番号の小さい未探索点 $3$ へ進みます。
探索点 $3$ から一番番号の小さい未探索点 $4$ へ進みます。
$4$ には未探索な隣接点がありませんので 赤い辺を通って $3$ へバックトラックします。
$3$ にも未探索な隣接点がありませんので更に 赤い辺を通って $2$ へバックトラックします。
$2$ から $5$ へ進んで終了です。
根 $0$ から一番番号の小さい未探索点 $1$ へ進みます。