Depth First Search vs. Breadth First Search
DFS vs BFS:
DFS vs BFS: DFS stands for Depth-first search. The algorithm starts at the root node and investigates each branch before backtracking. When a dead-end comes in any iteration, it employs a stack data structure to remember, fetch the next vertex, and begin a search. It visits the node in left-right-root order. Implementation of DFS is well simulated using the First In Last Out (FILO) order.
BFS stands for Breadth-first search. It traverses trees level-wise. It visits all the nodes from left to right at level k, before visiting any node at level k + 1. Implementation of BFS is well simulated using the First In First Out (FIFO) order.
While searching for a particular node in the tree, Breadth-first traversal is prefered when a node is close to the root. If the node to be searched is deep in the tree, depth-first search finds it quickly compared to BFS.
In general, BFS is considered to be slower compared to DFS.
In BFS, you can never be trapped into infinite loops whereas in DFS you can be trapped into infinite loops.
In the following table, we have compared both the problem-solving approaches: DFs vs BFS
Depth First Traversal | Breadth-First Traversal |
DFS explores the search as far as possible from the root node. | BFS explores the search level by level as close as possible from the root. |
DFS is implemented using stack, in LIFO order. | BFS is implemented using a queue, in FIFO order. |
DFS is faster than BFS. | BFS is slower than DFS. |
DFS needs less memory. | BFS needs more memory. |
Example : DFS Traversal : A-B-D-E-C | Example : BFS Traversal : A-B-C-D-E-F |
Applications of DFS : Cycle detection. Finding articulation point. Connectivity testing. Finding a path between vertex u to v. Finding spanning trees and forest. Topological sorting. | Applications of BFS : Find the shortest path. Single source shortest path. All pair shortest path. Spanning tree. Connectivity checking. |
Additional Reading: Read More