Trusted answers to developer questions
DFS vs. BFS
Free System Design Interview Course
Many candidates are rejected or down-leveled due to poor performance in their System Design Interview. Stand out in System Design Interviews and get hired in 2023 with this popular free course.
Two of the most popular tree traversal algorithms are breadth-first search (BFS) and depth-first search (DFS). Both methods visit all vertices and edges of a graph; however, they are different in the way in which they perform the traversal. This difference determines which of the two algorithms is better suited for a specific purpose.
A major difference between these algorithms is illustrated below:
Other key differences between the two algorithms are:
| BFS | DFS |
|---|---|
| BFS starts traversal from the root node and visits nodes in a level by level manner (i.e., visiting the ones closest to the root first). | DFS starts the traversal from the root node and visits nodes as far as possible from the root node (i.e., depth wise). |
| Usually implemented using a queue data structure. | Usually implemented using a stack data structure. |
| Generally requires more memory than DFS. | Generally requires less memory than BFS. |
| Optimal for finding the shortest distance. | Not optimal for finding the shortest distance. |
| Used for finding the shortest path between two nodes, testing if a graph is bipartite, finding all connected components in a graph, etc. | Used for topological sorting, solving problems that require graph backtracking, detecting cycles in a graph, finding paths between two nodes, etc. |
RELATED TAGS
dfs
bfs
depth first search
breadth first search
Copyright ©2023 Educative, Inc. All rights reserved
TRENDING TOPICS
Did you find this helpful?