BFS vs. DFS
Before looking at the differences between BFS and DFS, we first should know about
BFS and DFS separately.
What is BFS?
BFS stands for Breadth First Search. It is also known as level order traversal. The
Queue data structure is used for the Breadth First Search traversal. When we use the
BFS algorithm for the traversal in a graph, we can consider any node as a root node.
Let's consider the below graph for the breadth first search traversal.
Suppose we consider node 0 as a root node. Therefore, the traversing would be started
from node 0.
Once node 0 is removed from the Queue, it gets printed and marked as a visited node.
Once node 0 gets removed from the Queue, then the adjacent nodes of node 0 would
be inserted in a Queue as shown below:
,Now the node 1 will be removed from the Queue; it gets printed and marked as a
visited node
Once node 1 gets removed from the Queue, then all the adjacent nodes of a node 1
will be added in a Queue. The adjacent nodes of node 1 are 0, 3, 2, 6, and 5. But we
have to insert only unvisited nodes in a Queue. Since nodes 3, 2, 6, and 5 are unvisited;
therefore, these nodes will be added in a Queue as shown below:
The next node is 3 in a Queue. So, node 3 will be removed from the Queue, it gets
printed and marked as visited as shown below:
Once node 3 gets removed from the Queue, then all the adjacent nodes of node 3
except the visited nodes will be added in a Queue. The adjacent nodes of node 3 are
0, 1, 2, and 4. Since nodes 0, 1 are already visited, and node 2 is present in a Queue;
therefore, we need to insert only node 4 in a Queue.
, Now, the next node in the Queue is 2. So, 2 would be deleted from the Queue. It gets
printed and marked as visited as shown below:
Once node 2 gets removed from the Queue, then all the adjacent nodes of node 2
except the visited nodes will be added in a Queue. The adjacent nodes of node 2 are
1, 3, 5, 6, and 4. Since the nodes 1 and 3 have already been visited, and 4, 5, 6 are
already added in the Queue; therefore, we do not need to insert any node in the
Queue.
The next element is 5. So, 5 would be deleted from the Queue. It gets printed and
marked as visited as shown below:
Once node 5 gets removed from the Queue, then all the adjacent nodes of node 5
except the visited nodes will be added in the Queue. The adjacent nodes of node 5 are
1 and 2. Since both the nodes have already been visited; therefore, there is no vertex
to be inserted in a Queue.
The next node is 6. So, 6 would be deleted from the Queue. It gets printed and marked
as visited as shown below:
Before looking at the differences between BFS and DFS, we first should know about
BFS and DFS separately.
What is BFS?
BFS stands for Breadth First Search. It is also known as level order traversal. The
Queue data structure is used for the Breadth First Search traversal. When we use the
BFS algorithm for the traversal in a graph, we can consider any node as a root node.
Let's consider the below graph for the breadth first search traversal.
Suppose we consider node 0 as a root node. Therefore, the traversing would be started
from node 0.
Once node 0 is removed from the Queue, it gets printed and marked as a visited node.
Once node 0 gets removed from the Queue, then the adjacent nodes of node 0 would
be inserted in a Queue as shown below:
,Now the node 1 will be removed from the Queue; it gets printed and marked as a
visited node
Once node 1 gets removed from the Queue, then all the adjacent nodes of a node 1
will be added in a Queue. The adjacent nodes of node 1 are 0, 3, 2, 6, and 5. But we
have to insert only unvisited nodes in a Queue. Since nodes 3, 2, 6, and 5 are unvisited;
therefore, these nodes will be added in a Queue as shown below:
The next node is 3 in a Queue. So, node 3 will be removed from the Queue, it gets
printed and marked as visited as shown below:
Once node 3 gets removed from the Queue, then all the adjacent nodes of node 3
except the visited nodes will be added in a Queue. The adjacent nodes of node 3 are
0, 1, 2, and 4. Since nodes 0, 1 are already visited, and node 2 is present in a Queue;
therefore, we need to insert only node 4 in a Queue.
, Now, the next node in the Queue is 2. So, 2 would be deleted from the Queue. It gets
printed and marked as visited as shown below:
Once node 2 gets removed from the Queue, then all the adjacent nodes of node 2
except the visited nodes will be added in a Queue. The adjacent nodes of node 2 are
1, 3, 5, 6, and 4. Since the nodes 1 and 3 have already been visited, and 4, 5, 6 are
already added in the Queue; therefore, we do not need to insert any node in the
Queue.
The next element is 5. So, 5 would be deleted from the Queue. It gets printed and
marked as visited as shown below:
Once node 5 gets removed from the Queue, then all the adjacent nodes of node 5
except the visited nodes will be added in the Queue. The adjacent nodes of node 5 are
1 and 2. Since both the nodes have already been visited; therefore, there is no vertex
to be inserted in a Queue.
The next node is 6. So, 6 would be deleted from the Queue. It gets printed and marked
as visited as shown below:
