Depth-First Search (DFS) vs Breadth-First Search (BFS)
This post will cover the difference between the Depth–first search (DFS) and Breadth–first search (BFS) algorithm used to traverse/search tree or graph data structure.
1. Definition
The Depth–first search (DFS) algorithm starts at the root of the tree (or some arbitrary node for a graph) and explored as far as possible along each branch before backtracking.
The Breadth–first search (BFS) algorithm also starts at the root of the tree (or some arbitrary node of a graph), but unlike DFS, it explores the neighbor nodes first, before moving to the next-level neighbors. In other words, BFS explores vertices in the order of their distance from the source vertex, where distance is the minimum length of a path from the source vertex to the node.
2. Examples
The following graph shows the order in which the nodes are discovered in DFS:
The following graph shows the order in which the nodes are discovered in BFS:
3. Application
Below are the applications of DFS:
- Finding connected components in a graph.
- Topological sorting in a DAG(Directed Acyclic Graph).
- Finding 2/3–(edge or vertex)–connected components.
- Finding the bridges of a graph.
- Finding strongly connected components.
- Solving puzzles with only one solution, such as mazes.
- Finding biconnectivity in graphs and many more…
Below are the applications of BFS:
- Copying garbage collection, Cheney’s algorithm.
- Finding the shortest path between two nodes
u
andv
, with path length measured by the number of edges (an advantage over depth–first search). - Testing a graph for bipartiteness.
- Minimum Spanning Tree for unweighted graph.
- Web crawler.
- Finding nodes in any connected component of a graph.
- Ford–Fulkerson method for computing the maximum flow in a flow network.
- Serialization/Deserialization of a binary tree.
4. DFS and BFS for Trees
We may traverse trees in multiple ways in depth–first order or breadth–first order. The depth–first search for trees can be implemented using preorder, inorder, and postorder, while the breadth–first search for trees can be implemented using level order traversal.
Beyond these basic traversals, various more complex or hybrid schemes are possible, such as depth-limited searches like iterative deepening depth–first search.
5. Implementation Details
In BFS, we need to maintain a separate data structure for tracking the tree/graph nodes yet to be visited. This is easily done iteratively using the queue data structure.
In contrast to BFS, DFS doesn’t need any additional data structure to store the tree/graph nodes. The recursive implementation of DFS uses the call stack.
6. Time Complexity
The time complexity of both DFS and BFS traversal is O(V + E), where V
and E
are the total number of vertices and edges in the graph, respectively.
Please note that E
may vary between O(1) and O(V2), depending on how dense the graph is.
7. Memory Requirements
The memory is taken by DFS/BFS heavily depends on the structure of our tree/graph. The maximum memory taken by DFS (i.e., by call stack) is equal to the depth of the tree, and the maximum memory taken by BFS is equal to the width of the tree.
8. When to use DFS and BFS?
If we know the solution lies somewhere deep in a tree or far from the source vertex in the graph, use DFS. If we know the solution is not that far from the source vertex, use BFS.
If our tree is broad, use DFS as BFS will take too much memory. Similarly, if our tree is very deep, choose BFS over DFS.
Also See:
Depth First Search (DFS) – Interview Questions & Practice Problems
Breadth First Search (BFS) – Interview Questions & Practice Problems
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)