Here you will learn about difference between BFS and DFS algorithm or BFS vs. DFS.
Breadth First Search (BFS) and Depth First Search (DFS) are two popular algorithms to search an element in Graph or to find whether a node can be reachable from root node in Graph or not. And these are popular traversing methods also.
When we apply these algorithms on a Graph, we can see following types of nodes.
- Non-Visited nodes: These nodes not yet visited.
- Visited nodes: These nodes are visited.
- Explored nodes: A node is said to be explored when it was visited and all nodes which are connected (adjacent) to that node also visited.
Difference between BFS and DFS
| S. No. | Breadth First Search (BFS) | Depth First Search (DFS) |
| 1. | BFS visit nodes level by level in Graph. | DFS visit nodes of graph depth wise. It visits nodes until reach a leaf or a node which doesn’t have non-visited nodes. |
| 2. | A node is fully explored before any other can begin. | Exploration of a node is suspended as soon as another unexplored is found. |
| 3. | Uses Queue data structure to store Un-explored nodes. | Uses Stack data structure to store Un-explored nodes. |
| 4. | BFS is slower and require more memory. | DFS is faster and require less memory. |
| 5. | Some Applications:
|
Some Applications:
|
Example
Considering A as starting vertex.
Note: There are many sequences possible for BFS and DFS. Using permutations we can find how many are there.
Comment below if you found any information incorrect or missing in above tutorial for difference between dfs and bfs.
Very nice sir
Please explain why bfs is slower than bfs and why bfs takes more memory than dfs
very limited content.
This page helped me with my data engineering class. thanks for your content
Nice explanation .
Please explain why bfs is slower than bfs and why bfs takes more memory than dfs