BFS VS DFS

ER-DSP-BFS vs DFS Page 1

BFS vs DFS
S.
No.
Parameters BFS DFS
BFS stands for Breadth First DFS stands for Depth First
1. Stands for Search. Search.
BFS(Breadth First Search)
uses Queue data structure for DFS(Depth First Search) uses
2. Data Structure finding the shortest path. Stack data structure.
DFS is also a traversal
approach in which the traverse
BFS is a traversal approach in begins at the root node and
which we first walk through proceeds through the nodes as
all nodes on the same level far as possible until we reach
before moving on to the next the node with no unvisited
3. Definition level. nearby nodes.
BFS can be used to find a
single source shortest path in
an unweighted graph because, In DFS, we might traverse
in BFS, we reach a vertex through more edges to reach a
with a minimum number of destination vertex from a
4. Technique edges from a source vertex. source.
Conceptual BFS builds the tree level by DFS builds the tree sub-tree
5. Difference level. by sub-tree.
It works on the concept of It works on the concept of
6. Approach used FIFO (First In First Out). LIFO (Last In First Out).
BFS is more suitable for DFS is more suitable when
searching vertices closer to there are solutions away from
7. Suitable for the given source. source.
DFS is more suitable for game
or puzzle problems. We make
BFS considers all neighbors a decision, and the then
Suitable for first and therefore not suitable explore all paths through this
Decision for decision-making trees decision. And if this decision
8. Treestheirwinning used in games or puzzles. leads to win situation, we stop.
The Time complexity of DFS
The Time complexity of BFS is also O(V + E) when
is O(V + E) when Adjacency Adjacency List is used and
List is used and O(V^2) when O(V^2) when Adjacency
Adjacency Matrix is used, Matrix is used, where V stands
where V stands for vertices for vertices and E stands for
9. Time Complexity and E stands for edges. edges.
Visiting of Siblings/ Here, siblings are visited Here, children are visited
10. Children before the children. before the siblings.
11. Removal of Nodes that are traversed The visited nodes are added to
ER-DSP-BFS vs DFS Page 2
 BFS VS DFS

Traversed Nodes several times are deleted from the stack and then removed
the queue. when there are no more nodes
to visit.
DFS algorithm is a recursive
In BFS there is no concept of algorithm that uses the idea of
12. Backtracking backtracking. backtracking
DFS is used in various
BFS is used in various applications such as acyclic
applications such as bipartite graphs and topological order
13. Applications graphs, shortest paths, etc. etc.
14. Memory BFS requires more memory. DFS requires less memory.
BFS is optimal for finding the DFS is not optimal for finding
15. Optimality shortest path. the shortest path.
DFS has lesser space
complexity because at a time it
In BFS, the space complexity needs to store only a single
is more critical as compared path from the root to the leaf
16. Space complexity to time complexity. node.
BFS is slow as compared to DFS is fast as compared to
17. Speed DFS. BFS.
When the target is close to the When the target is far from the
18. When to use? source, BFS performs better. source, DFS is preferable.

ER-DSP-BFS vs DFS Page 3