BFS DFS Flashcards
What’s DFS stands for ?
Depth First Search
What’s BFS stands for ?
Breadth First Sreach
What’s BFS ?
It is a vertex-based technique for finding the shortest path in the graph.
BFS is a traversal approach in which we first walk through all nodes on the same level before moving on to the next level.
What’s DFS
is an edge-based technique.
DFS is also a traversal approach in which the traverse begins at the root node and proceeds through the nodes as far as possible until we reach the node with no unvisited nearby nodes.
Do this with DFS :
A
/ \
B C
/ / \
D E F
A, B, C, D, E, F
Do this with BFS :
A
/ \
B C
/ / \
D E F
A, B, C, D, E, F
Which data structures use DFS ? BFS?
BFS(Breadth First Search) uses Queue data structure for finding the shortest path.
DFS(Depth First Search) uses Stack data structure.
Which approach use DFS? BFS?
BFS: It works on the concept of FIFO (First In First Out).
DFS: It works on the concept of LIFO (Last In First Out).
Suitablity for both
BFS: BFS considers all neighbors first and therefore not suitable for decision-making trees used in games or puzzles.
DFS:DFS is more suitable for game or puzzle problems. We make a decision, and the then explore all paths through this decision. And if this decision leads to win situation, we stop.
Visiting of Siblings/ Children for both
In BFS : siblings are visited before the children.
In DFS : children are visited before the siblings.
Which one uses backtracking ?
DFS
Memory
BFS requires more memory.
Optimality for finding the shortest path
BFS is optimal for finding the shortest path.
DFS is not optimal for finding the shortest path.
Speed
BFS is slow as compared to DFS.
Tapping in loops
In BFS, there is no problem of trapping into finite loops.
In DFS, we may be trapped in infinite loops.
