11

これらのアルゴリズムがどのように機能するかを学びましたが、それらは何のために使用されますか？

それらを次の目的で使用しますか？

  • グラフで特定のノードを見つける、または
  • 最短経路を見つけるため、または
  • グラフでサイクルを見つけるには

？

どちらもすべてのノードにアクセスし、アクセス済みとしてマークを付けるだけですが、それを行う意味がわかりません。

私はここで私が学んでいることを少し失っています。

4

1 に答える 1

18

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

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

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

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

これは決して網羅的なリストではありません。これらのアルゴリズムにはあらゆる種類のアプリケーションがあり、より高度なアルゴリズムを検討し始めると、ビルディングブロックとしてDFSとBFSに依存していることに気付くことがよくあります。これは並べ替えに似ています。並べ替え自体はそれほど興味深いものではありませんが、値のリストを並べ替えることができると、より複雑なアルゴリズムのサブルーチンとして非常に役立ちます。

お役に立てれば！

于 2013-02-06T19:10:13.207 に答える