深さ優先探索の方法とその応用
1. 序章
このチュートリアルでは、深さ優先探索の3つのタイプ（インオーダー、ポストオーダー、プレオーダー）を詳しく見ていきます。 二分木で学んだことを適用します。これは、表現が簡単で、例を追跡しやすいためです。 ただし、これらの概念はどのタイプのグラフにも適用できます。
2. 二分木の例
以下の画像は、二分探索木の例です。 次のセクションでは、このツリーでのさまざまなトラバーサル方法を示します。
グラフを使用している場合は、最初に任意のノードを選択できることに注意してください。
3. インオーダートラバーサル（LNR）
インオーダートラバーサルには、ツリーをトラバースする順序を示すために、Left、Node、Rightを表すLNRの頭字語が付けられています。
順序どおりのトラバーサルを実行するには、次の手順を再帰的に実行します。
- 左側のサブツリーをトラバースします
- ルートノードをトラバースします
- 右側のサブツリーをトラバースします
ルート（6）から始めて、以下をチェックします。
- 左の子供がいますか？ そうなので、左の子（3）をチェックして、左の子がいるかどうかを尋ねます。 はい、ありますが、その子（2）には左の子がないため、トラバースできます
- これは順序どおりであるため、トラバースする次のノードは（2）のルートであり、ノード（3）の後に右の子（4）が続きます。
- ここで、（4）にはトラバースする独自の子がないため、左側のサブツリーのトラバースが終了し、ツリー（6）のルート、続いて右側のサブツリーのトラバースを続行できます。
正しいサブツリーをトラバースするには、次のことを確認します。
- ノード（19）に左側のノードがある場合は、それをトラバースします。 その場合、その左側のノード（12）には、トラバースする子がない左側のノード（7）があります。 したがって、トラバース（7）、次にそのルート（12）、次に右側のノード（15）をトラバースします。
- 最後に、左側のサブツリーの処理が終了した後、ノード（19）に戻り、右側のノード（30）に続いてノードをトラバースします。
このようにして、下の画像に表示されているのと同じ方法で、順序どおりのトラバーサルを使用してツリーのノードを完全にトラバースしました。 赤い数字は、ノードがトラバースされた順序を示していることに注意してください。
4. ポストオーダートラバーサル（LRN）
順序付け後のトラバーサル（左、右、ノード）では、別の順序を取り、代わりにルートから再帰的に次の手順を実行します。
- 左側のサブツリーをトラバースします
- 右側のサブツリーをトラバースします
- ルートノードをトラバースします
同じツリーをトラバースしましょうが、今回はポストオーダートラバーサルを使用して実行しましょう。
順序どおりのトラバースと同様に、ツリーのルートを確認し、トラバースを開始できる左の葉のノード（2）が見つかるまで、ツリーの左端のノードを確認することから始めます。 （2）をトラバースしたら、その右の兄弟ノード（4）をトラバースし、次にそのルート（3）をトラバースします。 そうすることで、左側のサブツリーのトラバースが終了し、同じ方法で右側のサブツリーに移動して、ツリーのルートを最後まで残すことができます。
ポストオーダートラバーサルには、CやC ++などのガベージコレクションが組み込まれていない一部の言語で便利なアプリケーションがあります。オブジェクトをメモリから解放するには、最初にその子を訪問してメモリから解放する必要があります両親を訪ねる前に。 そうしないと、ダングリングポインタとして知られているケースが発生します。 二分探索木からノードを削除する必要がある場合は、ポストオーダートラバーサルを使用することもできます。 まず、根の前にある葉をトラバースして削除する必要があります。
逆ポーランド記法（RPN）または後置記法として知られる表現評価の方法の一部として、ある時点でポストオーダートラバーサルも非常に人気がありました。 RPNは、数式を次のように表現するために使用されます。優先順位を維持するために角かっこを使用する必要はありません。 たとえば、RPNを使用すると、次の数式を表すことができます。
このような：
これは、計算が単純であり、マシンが解釈しやすいことを意味します。 歴史的に、PostScriptやForthなどの一部のヒューレットパッカード計算機および言語はRPNを利用し、非常に人気がありました。 現在、RPNには、数式の解析に関連する分野で非常に特殊なユースケースがあります。 構文ツリーのポストオーダートラバーサルを実行することにより、RPNを構築できます。
上記の数式を使用して、これがどのように機能するかの小さな例を見てみましょう。
まず、数式を式ツリーとして表します。
次に、ツリーのポストオーダートラバーサルを実行して、この式の接尾辞表記を取得します。
5. トラバーサルの事前注文（NLR）
最後に、事前注文トラバーサルについて学びましょう。 頭字語が示すように、pre-orderトラバーサルは最初にルートノードをトラバースし、次に左右のサブツリーをそれぞれトラバースします。 これは、次の手順を実行してツリーをトラバースすることを意味します。
- ルートノードをトラバースします
- 左側のサブツリーをトラバースします
- 右側のサブツリーをトラバースします
これがサンプルの二分探索木でどのように機能するかを見てみましょう。
この方法では、ルートノード（6）をトラバースすることから始め、次にその左側のサブツリーに移動します。 左側のサブツリーのルートは（3）であるため、トラバースした後、左側の子（2）をトラバースし、次に右側の子（4）をトラバースして、左側のサブツリーのトラバースを終了します。 最後に、同様の方法で、ルートノード（19）から始まり、その右の子（30）で終わる右のサブツリーをトラバースします。
事前注文トラバーサルは、二分探索木内の要素を検索するときに役立ちます。 ルートノードの値を使用して、次に右または左のサブツリーを検索する必要があるかどうかを判断できます。 さらに、データベースは通常、プレオーダートラバーサルを使用して、検索操作中にBツリーインデックスをトラバースします。
事前注文トラバーサルは、トポロジカルソートとして知られているものにも適用されます。 ノードがその子の前提条件または依存関係であると仮定すると、トポロジ的に順序付けられたツリーでの事前順序付けトラバーサルは、依存関係の前に依存関係を一覧表示するのに役立ちます。 トポロジカル順序付けには、プログラムの動的リンク、依存関係の解決、およびプロセッサのスケジューリングでのユースケースがあります。
これを使用する1つの特定の例は、Linuxmakefileユーティリティです。
6. 結論
結論として、深さ優先探索法をいくつか取り上げ、実世界でのそれらのアプリケーションについて学びました。 これらの方法については二分木のコンテキストで説明しましたが、グラフをトラバースするためにこれらの概念を使用することもできます。
実装の詳細にジャンプする準備ができたら、これらのメソッドのいくつかをJavaに実装する方法についてさらに学ぶことができます。
