BFS vs DFS: Understanding the Difference

While BFS uses queue to keep a track of the next location that it needs to visit, DFS uses stack to keep track of next location that it needs to visit. The main difference between BFS and DFS is that former goes by levels whereas latter takes path from the start to end vertex,

In this article on BFS vs DFS, we will be discussing the difference between the two algorithms. We will also discuss their features and advantages.

Table of Contents

• BFS vs DFS
• What is BFS?
• Features of Breadth-first Search Algorithm
• Advantages of BFS algorithm
• What is DFS?
• Features of Deapth-first Search Algorithm
• Advantages of DFS algorithm

BFS vs DFS: Differences

Both BFS and DFS are used for traversing a graph data structure. However, the two differ on several parameters, as mentioned in the tabular format:

What is Breadth-first search (BFS)?

Breadth-first search (BFS) refers to an algorithm to search tree data structure for any node that satisfies a given property. BFS begins the tree root and it explores every node at present depth before moving on to those nodes that are at the next depth level. It chooses the closest node and then investigates new node. Any node in graph can be root node while employing BFS for travel. 

Apart from trees, graphs might have cycles that may cause going back to the same node. The vertices are categorized into ‘visited’ and ‘unvisited’ nodes to prevent processing the node twice. BFS algorithm is used for searching a graph data structure or a tree for a node that meets a set of criteria. Breadth-first search is used for solving problems in graph theory. 

Explore free data structures and algorithm courses

Features of Breadth First Search Algorithm

BFS has the following features:

• Simple in implementation and understanding. 
• It can be easily parallelized, which allows taking advantage of multiple processors to speed up the search.
• Memory intensive since it keeps track of every node in the search tree.
• Slow since it expands every node at each level prior to moving to the next level.
• Helps in finding the sub-optimal solution as it does not explore every path via search tree.

Advantages of BFS

The following points explain the advantages of Breadth-first search:

• BFS is useful in locating nearby sites from the specific source location, 
• The breadth-first search algorithm is also used as traversal method in the peer-to-peer network for locating every adjacent node. Most torrent applications use this algorithm to locate “peers” and “seeds”  on the network.
• BFS is also used by web crawlers for building indexes for web pages. Considered one of the most important algorithms for indexing the web pages, it begins from source page and navigates across the page’s links. In this case, every web page is viewed as a node on the graph.
• The shortest route and least spanning tree are found via BFS.
• It is also used for calculating max flow in a flow system via Ford-Fulkerson approach.

What is Depth-first search (DFS)?

Depth-first search (DFS) is an algorithm that traverses data structures such as graphs or tress. DFS starts at root node and it examines every branch as far as possible before backtracking. DFS method traverses a network in deathward motion and uses stack data structure to acquire next vertex to initiate a search. A standard DFS implementation puts every vertex of graph in eith visited or not-visited category.

Features of DFS algorithm

Following are the features of Depth-First Search algorithm:

• DFS algorithm can be customized for discovering path between two specified vertices.
• It is a recursive algorithm used for traversing tree or graph data structure. 
• DFS uses stack data structure for its implementation
• Process of the Depth first search algorithm is similar to Breadth first search algorithm
• It is incomplete without a depth found. This means that you may be unable to find the solution even if it exists

Advantages of DFS

The following are the advantages of DFS algorithm:

• Requires less memory since it only stores stack of nodes on the path from root node to current node
• It can find solution with examining much search space and stop once found.
• Takes less time to reach goal node than BFS algorithm

Explore free online courses with certificates

_______________

Recently completed any professional course/certification from the market? Tell us what you liked or disliked in the course for more curated content.

Click here to submit its review.