BFSとdfsの主な違いは、BFSがレベルごとに進行し、DFSが最初に開始ノード（頂点）から終了ノード（頂点）までのパスをたどり、次に開始から終了までの別のパスなど、すべてのノードが訪問されるまでであることです。 さらに、BFSはノードの格納にキューを使用し、dfsはノードのトラバーサルにスタックを使用します。P>
bfsとDFSは、グラフの検索に使用されるトラバーシングメソッドです。 グラフトラバーサルは、グラフのすべてのノードを訪問するプロセスです。 グラフは、頂点に接続する頂点’V’と辺’E’のグループです。
コンテンツ: BFS Vs DFS
- Comparison Chart
- Definition
- Key Differences
- Conclusion
Comparison Chart
| Basis for comparison | BFS | DFS |
|---|---|---|
| Basic | Vertex-based algorithm | Edge-based algorithm |
| Data structure used to store the nodes | Queue | Stack |
| Memory consumption | Inefficient | Efficient |
| Structure | 幅と短さ | 幅と長さ |
| トラバーシングファッション | 最も古い未訪問の頂点が最初に探索されます。 | エッジに沿った頂点は、最初に探索されます。 |
| 最適性 | コストではなく、最短距離を見つけるのに最適です。 | 最適ではありません |
| アプリケーション | 二部グラフ、接続されたコンポーネント、およびグラフに存在する最短パスを調べます。 | は、二辺連結グラフ、強連結グラフ、非巡回グラフ、位相順序を調べます。 |
Bfsの定義
幅最初の検索（BFS）は、グラフで使用されるトラバース方法です。 これは、訪問した頂点を格納するためのキューを使用します。 この方法では、強調はグラフの頂点にあり、最初に1つの頂点が選択され、次に訪問されてマークされます。 次に、訪問された頂点に隣接する頂点が訪問され、順番にキューに格納されます。同様に、格納された頂点が1つずつ処理され、隣接する頂点が訪問されます。 ノードは、グラフ内の他のノードを訪問する前に完全に探索されます。
例
頂点がa、B、C、D、E、F、Gであるグラフがあります。Aを出発点とみなします。 プロセスに関係するステップは次のとおりです。
- 頂点Aが展開され、キューに格納されます。
- Aの頂点B、D、Gの後継者は、展開され、キューに格納されますが、頂点Aは削除されます。
- キューのフロントエンドにあるBは、後続の頂点EとFを格納するとともに削除されます。
- 頂点Dは、キューのフロントエンドで削除され、その接続されたノードFはすでに訪問されています。
- 頂点Gはキューから削除され、既に訪問されている後続のEがあります。
- EとFがキューから削除され、その後続の頂点Cがトラバースされてキューに格納されます。
- 最後にCも削除され、キューが空になりました。生成される出力は–A、B、D、G、E、F、Cです。
アプリケーション
bfsは、グラフに接続されたコンポーネントがあるかどうかを調べるのに役立ちます。 そしてまたそれは二部グラフの検出で使用することができます。
グラフの頂点が二つの互いに素な集合に分割されているとき、グラフは二部構成です。 二部グラフをチェックする別の方法は、グラフ内の奇数サイクルの発生をチェックすることです。 二部グラフに奇数サイクルを含めることはできません。
bfsは、グラフ内の最短経路を見つけることでも優れているネットワークとして見ることができます。
DFSの定義
深さ最初の検索（DFS）トラバースメソッドは、訪問した頂点を格納するためのスタックを使用します。 DFSはエッジベースの方法であり、頂点がパス（エッジ）に沿って探索される再帰的な方法で動作します。 ノードの探索は、別の未踏のノードが発見され、最も深い未踏のノードが最初にトラバースされるとすぐに中断されます。 DFSトラバース/各頂点を正確に一度訪問し、各エッジは正確に二度検査されます。Bfsと同様に、DFS操作を実行するために同じグラフを取ることができ、関連する手順は次のとおりです:
- スタックに探索されて格納される開始頂点としてAを考慮します。
- B aの後継頂点がスタックに格納されます。
- 頂点Bには2つの後継者EとFがあり、その中でアルファベット順にEが最初に探索され、スタックに格納されます。
- 頂点Eの後継、つまりGがスタックに格納されます。
- 頂点Gには2つの接続された頂点があり、両方とも既に訪問されているため、gはスタックから飛び出します。
- 同様に、E sも削除されました。
- 頂点Bはスタックの最上部にあり、その別のノード（頂点）Fが探索され、スタックに格納されます。
- 頂点Fには2つの後続のcとDがあり、それらの間にCが最初に走査され、スタックに格納されます。
- 頂点Cには、既にアクセスされている先行要素が1つしかないため、スタックから削除されます。
- Fに接続された頂点Dが訪問され、スタックに格納されます。
- 頂点Dには未訪問のノードがないため、Dは削除されます。
- 同様に、F、B、Aもポップされます。生成される出力は–A、B、E、G、F、C、Dです。
アプリケーション
DFSのアプリケーションは、二つのエッジ接続されたグラフ、強く接続されたグラフ、非循環グラフ、およびトポロジカル順序の検査が含まれています。
グラフが二つの辺が接続されていることと、その辺の一つが削除されても接続されたままであることは、二つの辺が接続されていることと呼ばれ このアプリケーションは、ネットワーク内の1つのリンクの障害が残りのネットワークに影響を与えず、まだ接続されているコンピュータネットワークでは、非常に便利です。
強く接続されたグラフは、頂点の順序付けられたペアの間にパスが存在しなければならないグラフです。 DFSは有向グラフで、順序付けられた頂点のすべてのペア間のパスを検索するために使用されます。 DFSは接続の問題を簡単に解決できます。
BFSとDFSの主な違い
- BFSは頂点ベースのアルゴリズムであり、DFSはエッジベースのアルゴリズムです。
- キューデータ構造はBFSで使用されます。 一方、dfsはスタックまたは再帰を使用します。
- メモリ空間はDFSで効率的に利用されますが、BFSでのスペース使用率は効果的ではありません。
- BFSは最適なアルゴリズムですが、DFSは最適ではありません。
- dfsは狭くて長い木を構築します。 逆に、BFSは広くて短いツリーを構築します。
結論
bfsとdfsは、グラフ検索技術の両方が同様の実行時間が、異なるスペース消費を持っている、DFSは、bfsは、メモリ内のすべてのノードを保持しDFSはより深い解を生成し、最適ではありませんが、解が密である場合はうまく機能しますが、最初は最適な目標を検索するBFSは最適です。p>