GeeksforGeeks

Breadth First Search

BFS står for Breadth First Search og er en vertexbaseret teknik til at finde den korteste vej i en graf. Den anvender en kø-datastruktur, som følger første ind først ud. I BFS vælges et toppunkt ad gangen, når det besøges og markeres, hvorefter dets tilstødende toppunkt besøges og gemmes i køen. Den er langsommere end DFS.
Ex-

 A / \ B C / / \ D E F

Output er:

A, B, C, D, E, F

Depth First Search

DFS står for Depth First Search og er en kantbaseret teknik. Den bruger Stack-datastrukturen og udfører to trin, først skubbes de besøgte hjørner ind i stakken, og hvis der ikke er nogen hjørner, fjernes de besøgte hjørner.
Ex-

 A / \ B C / / \ D E F

Output er:

A, B, D, C, E, F

BFS vs DFS

BFS står for Breadth First Search. DFS står for Depth First Search.

BFS(Breadth First Search) bruger Queue-datastruktur til at finde den korteste vej. DFS(Depth First Search) anvender Stack-datastruktur.

BFS kan bruges til at finde den korteste vej med en enkelt kilde i en uvægtet graf, fordi vi i BFS når et toppunkt med det mindste antal kanter fra et kildepunkt. I DFS kan det være, at vi gennemløber flere kanter for at nå et bestemmelsespunkt fra en kilde.

BFS tager først hensyn til alle naboer og er derfor ikke egnet til beslutningstræer, der anvendes i spil eller puslespil.

S.NO	BFS	DFS
BFS er mere velegnet til at søge efter hjørner, der er tættere på den givne kilde.	DFS er mere velegnet, når der er løsninger væk fra kilden.
DFS er mere velegnet til spil eller puslespilsproblemer. Vi træffer en beslutning og udforsker derefter alle stier gennem denne beslutning. Og hvis denne beslutning fører til en situation, hvor vi vinder, stopper vi.
	Tidskompleksiteten af BFS er O(V + E), når der anvendes Adjacency List, og O(V^2), når der anvendes Adjacency Matrix, hvor V står for vertices og E står for edges.	Tidskompleksiteten af DFS er også O(V + E), når Adjacency List anvendes, og O(V^2), når Adjacency Matrix anvendes, hvor V står for vertices og E står for edges.

Se også BFS vs DFS for Binary Tree for forskellene for en binær Tree Traversal.