Breadth-First Search (BFS) vs Depth-First Search (DFS)
Breadth-first search (BFS) and depth-first search (DFS) are strategies for searching and traversing tree and graph data structures.
In DFS, the algorithm visits a vertex and then recursively visits all vertices that are directly connected to this vertex.
In BFS, the algorithm visits all neighbors of a vertex (vertices of the same level) before moving to the next level.
| | DFS | BFS |
| Data structure | Stack (used for backtracking) | Queue |
| Memory used (with respect to depth of tree) | Linear | Exponential |
| Typical problems solved | Find shortest path, test if graph is bibpartitie | Find cycles or connections, topological sorting |
BFS generally requires more memory than DFS.