GeeksforGeeks

Breadth First Search

A BFS a Breadth First Search rövidítése, amely egy csúcsalapú technika a legrövidebb útvonal megtalálására a gráfban. Egy Queue adatszerkezetet használ, amely a first in first out elvét követi. A BFS-ben egyszerre egy csúcsot választunk ki, amikor azt meglátogatjuk és megjelöljük, majd a szomszédos csúcsokat meglátogatjuk és tároljuk a sorban. Lassabb, mint a DFS.
Ex-

 A / \ B C / / \ D E F

A kimenet:

A, B, C, D, E, F

Depth First Search

DFS jelentése Depth First Search egy él alapú technika. A Stack adatstruktúrát használja, két lépést hajt végre, először a meglátogatott csúcsokat tolja a verembe, másodszor ha nincs csúcs, akkor a meglátogatott csúcsokat kiugratja.
Ex-

 A / \ B C / / \ D E F

Kimenet:

A, B, D, C, E, F

BFS vs DFS

S.NO	BFS	DFS
	BFS jelentése Breadth First Search.	DFS jelentése Depth First Search.
	BFS(Breadth First Search) a legrövidebb út megtalálására Queue adatstruktúrát használ.	DFS(Depth First Search) Stack adatszerkezetet használ.
	A BFS egy súlyozatlan gráfban egyetlen forrásból származó legrövidebb út megtalálására használható, mert a BFS-ben egy forráscsomópontból minimális számú éllel érjük el a csúcsot.	A DFS-ben esetleg több élen haladunk át, hogy egy forrásból elérjünk egy célcsúcsot.
	A BFS alkalmasabb az adott forráshoz közelebbi csúcsok keresésére.	ADFS alkalmasabb, ha a forrástól távolabb vannak megoldások.
	A BFS először az összes szomszédot veszi figyelembe, ezért nem alkalmas játékokban vagy rejtvényekben használt döntési fákhoz.	AzDFS alkalmasabb játék- vagy rejtvényproblémákhoz. Hozunk egy döntést, majd ezen a döntésen keresztül feltárjuk az összes utat. És ha ez a döntés győzelmi helyzethez vezet, akkor megállunk.
	A BFS időbonyolultsága O(V + E), ha adjacencia listát használunk, és O(V^2), ha adjacencia mátrixot, ahol V a csúcsokat és E az éleket jelöli.	A DFS időbonyolultsága szintén O(V + E), ha Adjacency List-et használunk, és O(V^2), ha Adjacency Matrix-ot használunk, ahol V a csúcsokat és E az éleket jelöli.

A különbségeket lásd még: BFS vs DFS for Binary Tree for the differences for a Binary Tree Traversal.