Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

dfs
bfs
depth first search

DFS vs. BFS

Educative Answers Team

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:

svg viewer

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
Copyright ©2022 Educative, Inc. All rights reserved
RELATED COURSES

View all Courses

Keep Exploring