BFSとDFSの違いは何ですか

NS 主な違い BFSとDFSの間は BFSまたは幅優先探索はレベルごとに進み、DFSまたは深さ優先探索は開始ノードから終了ノードまでのパスをたどり、すべてのノードにアクセスするまで、開始から終了まで他のパスに移動します。

グラフは、データ要素をネットワークモデルとして配置する非線形データ構造です。グラフ内のノードは頂点と呼ばれ、エッジはこれらのノードを接続します。検索方法を使用して、ほとんどのグラフの問題を解決することが可能です。幅優先探索（BFS）と深さ優先探索（DFS）は、使用されている一般的な検索方法です。簡単に言うと、BFSはキューを使用し、DFSはスタックを使用します。

BFS、DFS

BFSとは

BFSはの略です 幅優先探索。キューを使用します。プロセスは次のとおりです。

例は次のとおりです。

図1：BFS

上の画像の開始頂点が1であると仮定します。1に接続されているノードは2と4です。したがって、1、2、4をキューに入れることができます。出力は1、2、4です。1の場合、残りの頂点はありません。したがって、キューから1を削除できます。これで、2に移動できます。2の隣接する頂点は3、5、および6です。したがって、3、5、および6をキューに入れることができます。出力は1、2、4、3、6です。これらの3つの数値に加えて、2に接続された隣接する頂点はありません。したがって、キューから2を削除できます。ここで、4に移動しましょう。4に隣接するノードは6だけです。すでにアクセスされています。 4の頂点はもうありません。したがって、キューから4を削除できます。キューが空になるまで、このプロセスを繰り返す必要があります。検索操作の終了を示します。

DFSとは

DFSはの略です 深さ優先探索。プロセスは次のとおりです。

隣接する未訪問の頂点にアクセスし、訪問済みとしてマークします。次に、それを出力に表示し、スタックにプッシュします。

隣接する頂点が見つからない場合は、スタックから頂点をポップアップします。

スタックが空になるまで、上記の2つの手順を続けます。

図2：DFS

開始頂点はAです。スタックにプッシュされます。隣接する頂点はBとEです。Bについて考えてみましょう。Bをスタックにプッシュできます。 Bに隣接するノードがないため、スタックからBをポップできます。出力はABです。Aに隣接する残りのノードはEなので、Eをスタックにポップできます。これで、出力はA BEになります。

Aに隣接するノードがないため、スタックから「A」をポップできます。 Eの隣接ノードはCとHです。ここでCについて考えます。Cをスタックにプッシュできます。出力はAB ECです。このプロセスはスタックが空になるまで続きます。検索操作を終了します。

BFSとDFSの違い

意味

BFS（幅優先探索）は、ルートノードからグラフのトラバースを開始し、すべての隣接ノードを探索するグラフトラバーサルアルゴリズムです。 DFS（深さ優先探索）は、グラフの最初のノードから始まり、必要なノードまたは子を持たないノードが見つかるまで、どんどん深くなっていくアルゴリズムです。したがって、これがBFSとDFSの主な違いです。