1. 序章


このチュートリアルでは、深さ優先探索、幅優先探索、ダイクストラのアルゴリズムの3つのアルゴリズムで経路を追跡する方法を示します。より正確には、最短経路を取得するいくつかの方法を示します。グラフ内の開始ノードとターゲットノードの間であり、それらの長さだけではありません。


2. 再帰的な深さ優先探索でパスをトレースする








深さ優先探索（DFS）には、再帰と反復の2つの実装があります。 前者のターゲットノードへの最短パスをたどるのは簡単です。 ターゲットノードに到達した後に再帰を展開するときに、ノードを保存するだけで済みます。




ここでは、配列として扱い、ノードを配列の前に追加して、開始ノードからターゲットの順にノードを配置しました。 別の方法は、スタックを使用することです。 ただし、順序が重要でない場合は、パスに個別のデータ構造を使用することを回避できます。 テストに合格するとすぐに現在のノードを出力し、再帰呼び出しから戻った後、に戻るまでforループで実行されたifステートメントで出力を続けることができます。 そうすれば、追加のメモリを使用することを回避できます。


2.1. 例


例として次のグラフを使用してみましょう。


からへの最短経路が必要です。 ノードの子を適切な順序で展開すると、DFSはとの間の最短パスを見つけます。


次に、展開した呼び出しに戻り、を取得するために追加します。 とで同じことを行うと、DFSは元の呼び出しに戻り、その呼び出しの前に追加して、最短パスとして提供します。


3. 反復深化優先探索でパスをトレースする


ただし、再帰的なDFSは、反復的なバリアントよりも遅い場合があります。




反復DFSでパスをトレースする方法は2つあります。 1つのアプローチでは、ノードにアクセスした後、その親が検索ツリーにあるノードを記憶します。 このようにして、ターゲットノードを見つけた後、親子階層に従ってパスを再構築できます。 もう1つの方法では、各ノードへのフルパスを保存します。 したがって、検索が終了すると、ターゲットノードにつながるものも使用可能になります。


再帰の有無にかかわらず、異なるデータ構造を使用して両方の手法を実装できます。 すべての方法は同じように機能し、どちらを選択するかは主に私たちの好みの問題です。


3.1. 「ファミリータイズ」を暗記する


重要なアイデアは、探索するノードの親を記憶することです。ノードを拡張し、その子を識別したとしましょう。 それぞれの子供について、その親が次のとおりであることを覚えておく必要があります。




3.2. パスの再構築


次に、パスを再構築するには、メモリを読み取ってターゲットの親を取得し、その後、開始ノードに到達するまでその親を取得するだけです。






このようにして、ターゲットノードから開始ノードへのパスを取得します。 逆の場合は、パスを逆に出力する必要があります。




3.3. メモリを実装する方法


さまざまなデータ構造を使用する親である情報を表すことができます。たとえば、へのポインタをに格納できます。 次に、メモリを読み取ることは、リンクリストをトラバースすることになります。


ハッシュマップを使用することもできます。一般的なアプローチは、各ノードに一意の正の整数をIDとして割り当て、IDをインデックスとして扱い、親子情報を配列に格納することです。 それがその配列だとしましょう。 次に、ノードの親は、IDが。であるノードです。 その親は、などです。


3.4. 例


これは、との間の最短バスに対応する順序でノードを拡張した場合に、DFSが大きくなることです。


3.5. 検索中にパスを記憶する


DFSの実行中に、現在アクティブなノードへのパスを追跡することもできます。 ノードを展開した後、その子へのパスが検索ツリー内のその子であることが記憶され、アルゴリズムがターゲットノードを識別すると、そのノードへのパスがすでに存在することがわかります。 したがって、記憶された情報から再構築する必要はありません ：




このアプローチは、再帰的DFSのパストレーシングに似ています。 ただし、は、内のすべてのノードへのフルパスを保持するため、より多くのメモリを使用します。 再帰的DFSでは、1つのパスのみを追跡します。


3.6. 例


このアプローチは、前の例では次のように機能します。


4. 幅優先探索でパスをトレースする


 DFSに使用したのと同じアプローチが幅優先探索（BFS）でも機能します。 DFSとBFSの唯一のアルゴリズムの違いは、キューにあります。前者はLIFOを使用し、後者はLIFOを使用します。 FIFO実装。 ただし、これによりBFSはDFSよりもはるかに多くのメモリを使用するため、パスの保存は最善の選択肢ではない可能性があります。 代わりに、親へのポインターを使用してノードを拡張するか、ハッシュマップを使用することを検討する必要があります。 この方法では、メモリのオーバーヘッドはそれほど発生しません。




アルゴリズム5と同じようにパスを再構築します。 注意すべき唯一のことは、アルゴリズム5の「 find the parent of   in 」という行は、BFSで機能するように「」として実装する必要があるということです。


4.1. 例


この例では、BFSがからへのパスを見つける方法は次のとおりです。


5. ダイクストラのアルゴリズムでパスをトレースする


DFSやBFSとは異なり、ダイクストラのアルゴリズム（DA）は、開始ノードからグラフ内の他のすべてのノードまでの最短経路の長さを検出します。 有限グラフに限定されますが、 DAは、DFSやBFSとは対照的に、正の重みのエッジを処理できます。


以前と同じアイデアをメモリに適用し、DAに適合させます。 アルゴリズムは、グラフ内のノードと開始ノードの間の最短パスの現在知られている長さを更新するとすぐにメモリを更新します。 配列は、パストレーシングを使用したDAの擬似コードでメモリの役割を果たします。






を使用して、と任意のノード間のパスを再構築できます。




ご覧のとおり、これはDFSで使用したのと同じ戦略です。


6. 結論


この記事では、深さ優先探索、幅優先探索、およびダイクストラのアルゴリズムでパスをトレースするいくつかの方法を示しました。