Motivation
Coddyの「深さ優先探索 - グラフアルゴリズム」コースのレッスン 2/9。
DFSは、1つのパスに専念して行けるところまで進み、その後、未探索の隣接ノードを持つ最後の頂点までバックトラック（後戻り）することでグラフを探索します。
なぜDFSを学ぶのか？
- 基本的： 閉路検出、トポロジカルソート、連結成分、その他多くのアルゴリズムの基礎となります。
- シンプルで低コスト： スタック（または再帰）と訪問済みマーカーを使用して、O(V + E)の時間で実行されます。
- 汎用的： 同じ走査で、「これら2つの頂点は接続されているか？」や「グラフにはいくつの独立した部分があるか？」といった問いに答えることができます。
結果の予測可能性を保つため、常に頂点の隣接ノードを昇順で訪問します。
自分で試してみよう
このレッスンにはコードチャレンジは含まれていません。
腕試しこのレッスンには短いクイズがあります。レッスンを始めて解答し、進捗を記録しましょう。
