Difference between BFS and DFS

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.

  1. Non-Visited nodes: These nodes not yet visited.
  2. Visited nodes: These nodes are visited.
  3. 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:

  • Finding all connected components in a graph.
  • Finding the shortest path between two nodes.
  • Finding all nodes within one connected component.
  • Testing a graph for bipartiteness.
Some Applications:

  • Topological Sorting.
  • Finding connected components.
  • Solving puzzles such as maze.
  • Finding strongly connected components.
  • Finding articulation points (cut vertices) of the graph.

Example

Considering A as starting vertex.

Difference between BFS and DFS

Image Source

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.

Category: DSA

Leave a Reply

Your email address will not be published. Required fields are marked *