Difference between BFS and DFS

What is BFS (Breadth-First Search)?

The vertex-based method known as BFS, or breadth-first search, locates the shortest path in a graph. It makes use of a queue data structure with first in, first out ordering. In BFS, just one vertex is chosen at a time to be visited, tagged, and then its neighboring vertex(es) are visited and queued. DFS is faster than it.

Example:

Let's say node 0 is the root node. As a result, node 0 would be the starting point for the traversal.

Node 0 is displayed and designated as a visited node after it has been taken out of the queue.

The neighboring nodes of node 0 would be added in a queue as indicated below whenever node 0 is withdrawn from the queue:

Node 1 will now be eliminated from the queue, printed, and designated as a visited node.

All of node 1's neighboring nodes will be added to a queue whenever node 1 is removed from it. Nodes 0, 3, 2, 6, and 5 are the nodes that are close to node 1. However, we must only add unvisited nodes to a queue. Nodes 3, 2, 6, and 5 will be put to a queue because they haven't been visited, as seen below:

3 is the following node in the queue. Node 3 is subsequently taken out of the queue, printed, and marked as visited as seen below:

All of node 3's nearby nodes, excluding the visited nodes, will be added to a Queue whenever node 3 is withdrawn from the Queue. Nodes 0, 1, 2, and 4 are the nodes that are next to node 3. Only node 4 needs to be added to a queue because nodes 0, 1, and 2 have previously been visited and are already present there.

The second node in the queue is now. Consequently, 2 would be eliminated from the queue. It prints and is noted as visited as follows:

All of node 2's neighboring nodes, excluding the visited nodes, will be added to a queue whenever node 2 is withdrawn from the queue. The nodes 1, 3, 5, 6, and 4 are situated next to node 2. We don't need to add additional nodes to the queue because nodes 1 and 3 have already been visited and nodes 4, 5, and 6 have already been added.

The 5th component is next. 5 would then be eliminated from the queue. It prints and is noted as visited as follows:

All of node 5's neighboring nodes, excluding the visited nodes, will be added to the Queue after node 5 is removed from it. Nodes 1 and 2 are nodes that are close to node 5. There is no vertex to be added to a queue since both nodes have already been visited.

Node 6 is the following. 6 would then be eliminated from the queue. It prints and is noted as visited as follows:

All of node 6's neighboring nodes, excluding the visited nodes, will be added to the queue after node 6 is withdrawn from it. Nodes 1 and 4 are nodes that are close to node 6. There isn't a vertex to be added to the queue because node 1 has already been visited and node 4 has already been added.

The fourth item in the queue is next. 4 would then be eliminated from the queue. It is printed and noted as having been viewed.

All of node 4's neighboring nodes, excluding the visited nodes, will be added to the queue after node 4 is withdrawn from it. The nodes 3, 2, and 6 are situated next to node 4. Since every neighboring node has already been visited, there isn't a vertex to add to the queue.

What is DFS (Depth First Search)?

Depth First Search, or DFS, is an edge-based method. It employs the Stack data structure and operates in two stages, pushing visited vertices onto the stack in the first and popping visited vertices in the second, if there are no vertices.

Example:

As the root node, think about node 0.

As illustrated below, we first add element 0 to the stack.

The nodes 1 and 3 are next to the node 0 in the network. Right now, we can only traverse one nearby node, either 1 or 3. Take node 1 as an example; as a result, 1 is added to a stack and written as seen below:

The neighboring vertices of node 1 will now be examined. 3, 2, 5, and 6 are the unexplored nearby node 1 vertices. Any of these four vertices can be taken into account. Assume we add node 3 to the stack as seen below:

Think about Node 3's unexplored neighboring vertices. Node 3's nearest unexplored vertices are 2 and 4. Either of the vertices, 2, or 4, can be used. Let's say we add vertex 2 to the stack as seen below:

Node 2's nearest unexplored vertices are 5 and 4. Either of the vertices, 5, or 4, can be chosen. Assume we pick vertex 4 and add it to the stack as per the example below:

We'll now think about Node 4's unexplored neighboring vertices. Node 4's neighboring vertex that hasn't been visited is node 6. As a result, element 6 is added to the stack as seen below:

We'll examine the nearby vertices of node 6 that haven't been visited after placing element 6 into the stack. Node 6 has no unvisited nearby vertices, thus we are unable to go past it. In this instance, we'll go backwards. As indicated below, the highest piece, number 6, would be removed from the stack:

The stack's top piece is number four. Node 4 gets removed from the stack as indicated below since there are no longer any unvisited nearby vertices.

2 is the next element in the stack from the top. We'll now examine Node 2's unexplored neighboring vertices. Since node 5 is the sole remaining unvisited node, it would be moved into the stack above node 2 and printed as illustrated below:

We will now examine the node 5's neighboring vertices, which have not yet been checked. We remove piece 5 from the stack because there isn't a vertex remaining to be visited, as seen below:

We are unable to go any farther, thus we must execute a retracing. The piece at the top of the stack would be popped out while going backward. As demonstrated below, we travel back to node 2 when the stack's top element, 5, has pushed out.

We will now examine Node 2's unexplored neighboring vertices. We retreat since there isn't a neighboring vertex left to visit. Backtracking causes the top element, 2, to be removed from the stack, and we then return to node 3, as illustrated below:

We will now examine the node 3's unexplored neighboring vertices. We retreat since there isn't a neighboring vertex left to visit. Backtracking would cause the top element, or 3, to be removed from the stack, and we would then return to node 1, as illustrated below:

After removing element 3, we will examine the surrounding vertices of node 1 that have not yet been visited. Backtracking will be used because there are no more vertex locations to visit. Backtracking causes the top element, 1, to be removed from the stack, and we then return to node 0, as illustrated below:

We will examine node 0's neighboring vertices, which have not yet been checked. We retreat since there isn't a neighboring vertex left to visit. In this case, the stack would only have one element remaining, or 0: the example below.

According to the figure above, the stack is empty. Therefore, we must halt the DFS traversal at this point, and the items printed represent the outcome of the DFS traverse.

Differences between BFS and DFS

S. No.	Parameters	BFS	DFS
1.	Stands for	Breadth First Search is referred to as BFS.	Depth First Search is referred to as DFS.
2.	Data Structure	The shortest path is discovered using the Queue data structure via BFS (Breadth First Search).	Stack data structure is used by DFS (Depth First Search).
3.	Definition	BFS is a traversal method where we travel through every node on one level before moving on to the next.	A traversal strategy like DFS starts from the root node and travels as far across the nodes as it can until it reaches the node that has no unvisited neighboring nodes.
4.	Technique	Because BFS requires that we arrive at a vertex from a source vertex with the fewest possible edges, it may be used to identify a single source shortest path in an unweighted graph.	In DFS, we could travel along multiple edges from a source to a destination vertex.
5.	Conceptual Difference	BFS creates the tree one level at a time.	DFS constructs the tree one subtree at a time.
6.	Approach used	It operates on the FIFO principle (First in First Out).	It utilizes the LIFO principle (Last In First Out).
7.	Suitable for	BFS works better when looking for vertices that are near a certain source.	DFS works better when there are alternatives to the source.
8.	Suitable for Decision Tress	BFS prioritizes neighbors, making it unsuitable for decision trees used in games or puzzles.	For issues in games or puzzles, DFS is more appropriate. After making a choice, we consider all possible outcomes. And if making this choice results in a win, we cease.
9.	Time Complexity	BFS's time complexity, where V stands for vertices and E for edges, is O(V + E) when an adjacency list is used and O(V2) when an adjacency matrix is employed.	When using an adjacency list or matrix, the time complexity of DFS is also O(V + E), where V stands for vertices and E for edges, and O(V2) when using an adjacency matrix.
10.	Visiting of Siblings/ Children	In this case, siblings are seen before kids.	In this case, siblings come here before children.
11.	Removal of Traversed Nodes	Repeatedly traversed nodes are removed from the queue.	When there are no more nodes to visit, the visited nodes are added to the stack and subsequently deleted.
12.	Backtracking	Backtracking is not a notion in BFS.	Recursive algorithm DFS employs the concept of backtracking.
13.	Applications	BFS is utilized in a variety of applications, including shortest path, bipartite graphs, and others.	DFS is utilized in many applications, including topological order and acyclic graphs, among others.
14.	Memory	It takes more memory for BFS.	Less RAM is needed for DFS.
15.	Optimality	The shortest path can be discovered best with BFS.	The shortest path cannot be found with DFS at its best.
16.	Space complexity	When it comes to BFS, space complexity is more important than temporal complexity.	DFS has a lower storage complexity since it only has to store one path from the root to the leaf node at a time.
17.	Speed	BFS is less fast than DFS.	DFS moves more quickly than BFS.
18.	When to use?	BFS works best when the source and target are close to one other.	DFS is advantageous when the target is remote from the source.

 

Blog by

Tushar Khandvikar