In this post, we will see the difference between Depth first search (DFS) and Breadth first search (BFS) algorithm which are 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 explores as far as possible along each branch before backtracking.
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 source vertex to the node.
2. Examples
Below graph shows order in which the nodes are discovered in DFS.
Below graph shows 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 bi-connectivity 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 and v, with path length measured by 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
Trees may be traversed in multiple ways in depth-first order or breadth-first order. Depth-first search for trees can be implemented using pre-order, in-order, and post-order while 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 Queue data structure.
In contrast to BFS, DFS don’t need any additional data structure to store the tree/graph nodes. The recursive implementation of DFS uses the recursive call stack.
6. Time Complexity
The time complexity of both DFS and BFS traversal is O(N + M) where N is number of vertices and M is number of edges in the graph.
Please note that M may vary between O(1) and O(N2), depending on how dense the graph is.
7. Memory Requirements
The memory taken by DFS/BFS heavily depends on the structure of our tree/graph. The maximum memory taken by DFS (i.e. by recursion 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 graph, use DFS. If we know the solution is not that far from the source vertex, use BFS.
If our tree is very wide, use DFS as BFS will take too much memory. Similarly if our tree is very deep, choose BSF over DFS.
Depth-first Search (DFS) Practice Problems
Breadth-first Search (BFS) Practice Problems
(2 votes, average: 5.00 out of 5)
Loading...
Thanks for reading.
Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
Leave a Reply