GeeksforGeeks

Breadth First Search

BFS は Breadth First Search の略で、グラフの最短経路を見つける頂点ベースのテクニックです。 先入れ先出しのQueueデータ構造を用いる。 BFSでは、一度に1つの頂点が選択され、それが訪問されマークされると、その隣接頂点が訪問されキューに格納される。
Ex-

 A / \ B C / / \ D E F

出力は:

A, B, C, D, E, F

Depth First Search

DFS は Depth First Search の略で、辺ベースの技術です。 スタックデータ構造を使用し、2つの段階を実行します。最初に訪問した頂点はスタックにプッシュされ、次に頂点がない場合は訪問した頂点がポップされます。NO

BFS DFS

BFS は Breadth First Search、

DFS は Depth First Search。

BFS (Breadth First Search) では Queue データ構造により最短経路を求めることができる。

DFS(Depth First Search)はStackデータ構造を使う。 BFSは重みのないグラフでシングルソース最短経路を求めるのに使える。BFSではソース頂点から最小のエッジ数で頂点に到達するからだ。 DFSでは、送信元から送信先の頂点に到達するために、より多くの辺を通過する可能性がある。 BFSは与えられた送信元に近い頂点を探すのに適している。 BFSはすべての隣接点を最初に考慮するので、ゲームやパズルで使われる決定木には適さない。 DFS はゲームやパズルの問題に適している。 決定を行い、その決定を通るすべての経路を探索する。 そして、この決定が勝利の状況をもたらすならば、我々は停止する。 BFSの時間計算量は、隣接リストを使う場合はO(V + E)、隣接行列を使う場合はO(V^2)（Vは頂点、Eは辺を表す）となる。 DFSの時間計算量も、Adjacency Listを使った場合はO(V + E)、Adjacency Matrixを使った場合はO(V^2)となります（Vは頂点、Eは辺）。

二分木トラバーサルでの違いについてBFSとDFSも参照して下さい。