BFSとDFSは、どちらもグラフの結果に不可欠です。 BFSは幅優先探索の略で、DFSは深さ優先探索の略です。どちらも2つの違いがあります。どちらも機能に異なるデータ構造を使用しています。1つはキューデータ構造を使用し、もう1つはスタックデータ構造を使用しています。
BFSとDFS
BFSとDFSの主な違いは、幅優先探索は、グラフ内の最短経路を示すのに役立つ頂点に基づく手法であるということです。一方、DFSまたは深さ優先探索はエッジに基づく手法です。 BFSは、キューのデータ構造に依存する手法です。一方、DFSはスタックデータ構造に依存します。
BFSは、キューデータ構造を使用してグラフ内の最短ルートを把握するために適用される手法です。ソースの近くの領域内の頂点を見つけるのに適しています。 DFSとは異なり、パズルやゲームで見られる意思決定ツリーにうまく適用することはできません。
DFSは、スタックデータ構造を使用してグラフ内の最短経路を見つけるために適用される手法です。ソリューション内のソースから遠く離れた領域に適しています。 BFSとは異なり、ゲームの意思決定や問題解決に適しています。
BFSとDFSの比較表
| 比較のパラメータ | BFS | DFS |
| 完全な形式と定義 | BFSはBreadth-FirstSearchの略です。これは、グラフ内の最短ルートを見つけるために使用される頂点に基づく手法です。 | DFSはDepthFirstSearchの略です。これは、グラフ内の最短ルートを見つけるためのエッジに基づく手法です。 |
| データ構造への依存 | 幅優先探索またはBFSは、キューデータ構造を使用してグラフ内の最短経路を計算します。 | 深さ優先探索またはDFSは、スタックデータ構造を使用してグラフ内の最短経路を計算します。 |
| 用途 | 重み付けされていないグラフでは、頂点ソースからのエッジの数が最も少ないため、単一のソースの最短パスを見つけるために使用されます。 | DFSでは、任意のソースから宛先または頂点に到達するために、より多くのエッジを通過する必要があります。 |
| 適合領域 | 頂点を見つけるのに適した領域は、ソースの至近距離内にあります。ゲームに存在する決定木を作成するのには適していません。 | その適合領域は、ソースから遠く離れたソリューション内にあります。ゲームやパズルの意思決定や問題に適しています。 |
| 機構 | この手法では、訪問中に一度に1つの頂点が選択され、マークが付けられた後、隣接する頂点が訪問され、キューにストックされます。 | 訪問した頂点はスタックに入れられ、頂点がない場合は、訪問した頂点がポップされます。 |
BFSとは何ですか？
BFSの助けを借りて、グラフは動きに向かってパンを横切って移動します。次の頂点をフェッチすることを忘れないようにするために、この手法ではキューが使用されます。これは、反復で行き止まりに直面したときに発生します。それはすべての隣人を広範に包含するので、決定木には考慮されません。 DFSよりも比較的遅いです。 BFSアルゴリズムBFSの時間計算量は、隣接リストの時間中はO（V + E）であり、隣接行列の時間中はO（V ^ 2）です。ここで、Eはエッジを表し、Vは頂点を表します。グラフのBFSアルゴリズムは、さまざまな分野で使用できます。
BFSは、ピアツーピア接続ですべての隣接ノードをコイニングするために非常に使用されます。インデックスは、検索エンジンのクローラーによるこの手法の助けを借りて構築されます。ソースページから新しいページまで、関連するすべてのリンクを見つけるのに役立ちます。 GPSナビゲーション機能を利用して近隣の場所を見つけるために必要です。 BFSアルゴリズムは、ネットワークで一部のパケットをブロードキャストするときに使用されます。パスファインディングのアルゴリズムにはBFSが含まれます。この手法の助けを借りて、ネットワークの最高のフローは、フォード-ファルカーソンアルゴリズムで見つけることができます。
DFSとは何ですか？
DFSの助けを借りて、グラフは深さ方向の動きでトラバースされます。このテクニックでは、スタックを使用して、前のポイントの隣にポイントを取得することを思い出させます。検索は、反復の発生中に実行されます。決定木の間に、決定を補強するためにさらにトラバースを行う必要があります。結論として、勝利は認められます。 BFSよりも速度が比較的速いです。 DFSの時間計算量は、隣接リストではO（V + E）、隣接行列ではO（V ^ 2）です。ここで、Eはエッジを表し、Vは頂点を表します。 DFSはさまざまな分野で広く使用されています。
重み付けされていないグラフでDFSが実行されると、最短パスツリーペアごとに最小スパニングツリーが開発されます。グラフのサイクルを識別するために適用できます。 BFSで1つのバックエッジが見つかった場合、1つのサイクルがあります。この手法を使用すると、uとvまたは2つの頂点間のパスを見つけることができます。トポロジカルソートにはDFSアルゴリズムが使用されます。これは、特定のグラフで強くリンクされているコンポーネントを判別するために使用できます。各頂点の間にパスがある場合、コンポーネントは強く接続されるように造られています。
BFSとDFSの主な違い
結論
したがって、BFSとDFSは明らかに異なると言えます。 BFSは、キューデータ構造を使用して最短パスを見つけるためにグラフで使用され、DFSは、スタックデータ構造を使用して最短パスを見つけるためにグラフで使用されます。 BFSは、訪問中に単一の頂点を選択し、マークされた後、隣接する頂点が訪問され、キューに収集されます。一方、DFSでは、訪問した頂点がスタックに含まれ、頂点がない場合、頂点がポップされます。 BFSの手法は頂点に基づいており、DFSの手法はエッジに基づいています。
