BFSとDFSの目的は何ですか？

Question

私はこれらのアルゴリズムがどのように機能するのかを学んだのですが、そのアルゴリズムは何のために使われていますか？

我々はそれらを使用してください：

• はグラフ

サイクルを見つけるために、最短経路や

を見つけるために、グラフや

内の特定のノードを見つけますか？

両方とも、すべてのノードにアクセスして訪問したことをマークしていますが、その点についてはわかりません。

私はここで勉強しているものを紛失しています。

Answer 1

BFSとDFSは、さまざまな目的に使用できるグラフ検索アルゴリズムです。

2つの検索手法の1つの共通アプリケーションは、特定の開始ノードから到達可能なすべてのノードを識別することです。たとえば、それぞれが数台の他のコンピュータにネットワーク接続されているコンピュータの集まりがあるとします。特定のノードからBFSまたはDFSを実行すると、元のコンピュータが直接的または間接的に通信できるネットワーク内の他のすべてのコンピュータが検出されます。これらは、マークされたコンピュータです。

BFSは、特に、重み付けされていないグラフ内の2つのノード間の最短経路を見つけるために使用できます。たとえば、ネットワーク内のあるコンピュータから別のコンピュータにパケットを送信し、そのコンピュータが互いに直接接続されていないとします。できるだけ早く目的地に到着するためにはどのようなルートに沿ってパケットを送るべきですか？ BFSを実行し、各反復で各ノードが "親"ノードへのポインタを格納すると、開始ノードから横断する必要があるリンクの数を最小限に抑えるグラフ内の他のノードまでのルートを見つけることになります宛先コンピュータに到達する。

DFSは、より複雑なアルゴリズムでサブルーチンとしてよく使用されます。例えば、強連結成分を計算するためのTarjanのアルゴリズムは深さ優先検索に基づいている。多くの最適化コンパイラ技法は、適切に構成されたグラフに対してDFSを実行して、特定の一連の操作を適用する順序を決定します。深さ優先探索は、迷路生成でも使用できます。ノードのグリッドを取得し、各ノードを隣接ノードにリンクすることによって、グリッドを表すグラフを構築できます。このグラフ上でランダムな深さ優先検索を実行すると、正確に1つの解決策を持つ迷路が作成されます。

これは完全なリストではありません。これらのアルゴリズムにはあらゆる種類のアプリケーションがあります。より高度なアルゴリズムを探究し始めると、DFSとBFSをビルディングブロックとして使用することがよくあります。ソートと似ています。ソート自体は興味深いわけではありませんが、値のリストをソートできるということは、より複雑なアルゴリズムのサブルーチンとして非常に便利です。

希望すると便利です。