BFS :
It stands for Breadth First Search.
It is a traversal algorithm which uses level order traversal which means all nodes of the same level are traversed first before moving on to the next level nodes.
It uses Queue for it's implementation(First In First Out/FIFO) instead of Stack to find the shortest path.
BFS covers all of it's neighbors while traversing.
It is widely preferred in programming over DFS as it is better than using recursion in some cases.
It is optimal as it covers shallowest nodes first and chances of missing the shortest path are less.
It’s precisely the space complexity that makes BFS impractical even though it’s complete and optimal in the cases where DFS isn’t.
It can require a lot of space and will prove to be inefficient if the branching factor is too large or the goal is deep.
Example:
1 //levels
/ \
2 4
/ / \
3 5 6
Output : 1 2 4 3 5 6 as it follows Level Order Traversing
1 -> 1
--------------
/ \
2 -> 2 4
---------------
/ / \
3 -> 3 5 6
DFS :
It stands for Depth First Search.
It is a traversal algorithm which uses stack data structure which works on the LIFO (Last In First Out) principle.
In DFS, all nodes are traversed in a depth-ward manner and then backtracking is performed to get back to the root.
It uses Stack for it's implementation instead of Queue to find the shortest path.
DFS is better when target is far from source
It reaches deep nodes faster than BFS.
It uses recursion to get to the end with base conditions.
DFS isn’t an optimal algorithm.
It's time complexity is high as compared to DFS.
DFS discovers a longer path first to reach to the goal.
BFS is impractical because of the high order of its space complexity. That is why DFS is used more often.
Example:
1 //depth
/ \
2 4
/ / \
3 5 6
Output : 1 2 3 4 5 6
.
1 -> 1.
/. \ .
2 -> 2 . 4.
/ . /. \ .
3 -> 3 . 5. 6.
. . .
You should know recursion, stack ,queue, priority queue, 0 and 1 based indexing before moving on to solve BFS and DFS questions.
Comments