GeeksforGeeks

Breadth First Search

BFS je zkratka pro Breadth First Search, což je vrcholová technika hledání nejkratší cesty v grafu. Používá datovou strukturu Queue, která se řídí pravidlem first in first out. V BFS je vybrán vždy jeden vrchol, když je navštíven a označen, pak jsou navštíveny jeho sousední vrcholy a uloženy do fronty. Je pomalejší než DFS.
Ex-

 A / \ B C / / \ D E F

Výstup je:

A, B, C, D, E, F

Depth First Search

DFS je zkratka pro Depth First Search, což je technika založená na hranách. Používá datovou strukturu Stack, provádí dvě fáze, první navštívené vrcholy se strčí do zásobníku a druhá, pokud tam nejsou žádné vrcholy, pak se navštívené vrcholy vysypou.
Ex-

 A / \ B C / / \ D E F

Výstup je:

A, B, D, C, E, F

BFS vs DFS

S.NO	BFS	DFS
	BFS znamená Breadth First Search.	DFS znamená Depth First Search.
	BFS(Breadth First Search) používá datovou strukturu Queue pro nalezení nejkratší cesty.	DFS(Depth First Search) používá datovou strukturu Stack.
	BFS lze použít k nalezení jediné zdrojové nejkratší cesty v neváženém grafu, protože v BFS dosáhneme vrcholu s minimálním počtem hran ze zdrojového vrcholu.	V DFS můžeme projít více hran, abychom dosáhli cílového vrcholu ze zdroje.
	BFS je vhodnější pro hledání vrcholů, které jsou blíže danému zdroji.	DFS je vhodnější, když existují řešení vzdálená od zdroje.
	BFS uvažuje nejprve všechny sousedy, a proto není vhodný pro rozhodovací stromy používané ve hrách nebo hádankách.	DFS je vhodnější pro řešení problémů her nebo hádanek. Učiníme rozhodnutí a poté prozkoumáme všechny cesty přes toto rozhodnutí. A pokud toto rozhodnutí vede k vítězné situaci, zastavíme se.
	Časová složitost BFS je O(V + E) při použití seznamu přilehlostí a O(V^2) při použití matice přilehlostí, kde V znamená vrcholy a E hrany.	Časová složitost DFS je také O(V + E), když se použije Adjacency List, a O(V^2), když se použije Adjacency Matrix, kde V znamená vrcholy a E znamená hrany.

Pro rozdíly pro binární strom se podívejte také na BFS vs DFS pro binární strom.