BFS and DFS

Not familiar??? Let’s discuss Breadth-First-Search (BFS) and Depth-First-Search (DFS) algorithms here!!!

DFS???

Here, we do not explore vertices around the next level but go to the depth of the graph. We go deeper and explore the nodes connected to the source node, we started traversing, until the last node.

We often get fooled by looking at the node levels in a DFS graph, when traversing. We assume that if the nodes are located above each other, they are at different layers and not in the depth of the search. DFS is not traversing the layers of the graph but going deeper from a source node to the last node.

Therefore, do not get confused by looking at how the graph is drawn but consider the nodes connected to the source node and explore deeper into that path.

For a DFS, we cannot use a queue as the data structure!!! Why??? Because DFS means we go deeper from the source node/a specific node and traverse back (return to the same node). The clear rule is LIFO (Last-in-First-out), the element that enters last will be removed first. Therefore, the right candidate is the Stack!!!

But, the queue follows the FIFO (First-in-First-out) rule; the element that enters the first will be removed first. More applicable for the BFS. In BFS, all the nodes in the same level have to be explored first, before moving to the next layer /level.

Rules for DFS on an Undirected Graph

• Traversing can start with any vertex (no specific rule saying that this should be the initial vertex/source node).
• From the source node, traverse each adjacent vertices in that path till the last node (node that does not have an edge!!!) — assume the traversal as going deep down a tree branch!!!
• When there is a node connected to two other nodes or more, any path can be taken, (no specific rule saying that traverse right then left!!!), i.e. any one node’s path can be followed till there are no adjacent, unvisited vertices of the last node.
• When traversing a specific path in DFS, we always check for the adjacent unvisited vertices of the current node(plural of vertex, vertex means node).

Let’s look at an example!!!

DFS Graph

Steps for DFS Traversal

1. Start from any vertex, we will start from Vertex 0.
2. Initialize a Stack, and push node 0 to the Stack.
3. There are two paths that can be taken from node 0, take any one path, i.e. 1 or 3 (because these are the adjacent vertices to node 0).
4. We will take node 1’s path. Push node 1 to the Stack.
5. Node 1 has nodes 0, 3, 2, 6, and 5 as adjacent vertices. But we cannot go in node 0’s path, since it is already visited and pushed to the Stack. So, the options remaining are 3, 2, 6, and 5. We will take node 3’s path and push node 3 to the Stack.
6. Node 3 has nodes 0, 1, 2, and 4 as adjacent vertices. Nodes 0 and 1 are already visited and pushed to Stack. So the remaining vertices are 2 and 4. We will take node 2’s path. Push node 2 to the Stack.
7. Node 2 has nodes 1, 3, 4, and 5 as adjacent vertices, but 1 and 3 are visited and pushed to Stack. We will take node 4’s path and push it to the Stack.
8. Node 4 has nodes 3, 2, and 6 as adjacent nodes, but only node 6 is unvisited, so taking node 6’s path and pushing it to Stack.
9. Node 6 has nodes 1 and 4 as adjacent vertices but both are visited and already in the Stack. There are no other unvisited adjacent vertices to node 6 and we need to traverse backward.

Snap of the Stack before traversing backward

When traversing backward, we will start from node 6 but how to continue??? We will use the Stack and pop out elements from it to traverse further in the graph!!! Here, upon each node, we have to check if that node has any adjacent unvisited nodes (to see if all the nodes have been traversed!!!).

Note: While popping out nodes from the Stack, during backward traversal (we use the stack to do this, because also to keep track of the traversal), did you see that you are popping out the last node you pushed to the stack!!! This is why DFS implementation follows the LIFO principle, and as a result, the Stack as its data structure.

1. Pop-out node 6 from the Stack, since it is the current top element of the Stack.
2. The next top element is node 4, we have to check if it has any unvisited adjacent vertices. Node 4 has nodes 2, 3, and 6 and all are visited. Therefore, we will pop out node 4 from the Stack.
3. The next top element in the Stack is node 2. Node 2 has node 5 as an adjacent vertex that has not been visited, therefore, node 5 will be pushed to the Stack.
4. The current top element of the Stack is node 5, are there any adjacent unvisited vertices of node 5??? No, then we need to traverse backward from here.
5. Pop-out node 5 from Stack.
6. The top element in the Stack now is node 2. Are there any adjacent vertices to node 2 which has not been visited??? No. Therefore, pop out node 2 from the Stack.
7. The top element is node 3, nodes 0, 1, 2, and 4, which are adjacent to it are all visited. So, pop out node 3 from the Stack.
8. Now, the top element is node 1, all adjacent vertices to it are visited and we will pop it out from the Stack.
9. Finally, node 0 is the only element and the top element in the Stack, Are there any adjacent vertices of 0 still unvisited??? No, so pop out node 0 from the Stack.

When the Stack becomes empty, it is the indication that we need to stop the DFS traversal.

Snap of Stack transition

So, one valid Depth-First-Search for the above graph is :

One valid traversal

There can be alternative valid traversals for the above graph based on the path you choose to take e.g. initially, at node 0, if you choose to follow node 3’s path instead of node 1 (as in the example above), then the traversal will be 0 3 …… and goes on!!!

Hooray!!! Hope you understood the Depth-First-Search!!! Let’s look at BFS now!!!

BFS???

This is Breadth-First, where the graph is traversed layer by layer. All the nodes in each layer are explored before moving to the next layer.

When implementing BFS, the queue is used as the data structure. Queue follows the FIFO (First In First Out) rule. Why FIFO??? Let’s discuss the rules of BFS first!!!

Rules for BFS on an Undirected Graph

1. Traversing can start with any vertex (There is no specific rule saying that this should be the initial vertex/source node).
2. From the source node/root node, we need to explore all the nodes connected to it (all adjacent vertices have to be explored).
3. The nodes connected to the initial node can be visited in any order.
4. When exploring the nodes connected to a particular node, it has to be checked if that node is unvisited, to be inserted into the queue.

Note: Finding out adjacent vertices of any node is known as the exploration of that node!!!

There are 2 types of graphs, Directed and Undirected Graph.

Directed Graphs follow specific directions according to which the graph is traversed. Each vertex leads to the next based on a direction. Directions are specified on the graph!!!

Undirected Graphs do not have directions specified and can be traversed in any direction.

Let’s check an example!!!

BFS Graph

Steps for BFS Traversal

1. Start from any vertex, we will start from Vertex 0.
2. Initialize a Queue, and insert node 0 to the Queue.
3. Now, we remove node 0 from the Queue, to mark it as “visited”.
4. Then, we will explore the nodes connected or adjacent to node 0. In this case, nodes 1 and 3 are connected to node 0 and so are inserted into the queue. These nodes can be inserted in any order into the queue.
5. At the moment, we have nodes 1 and 3 in the queue, so, as per the FIFO rule (remove the node that was inserted first), node 1 will be removed from the queue and marked as “visited”.
6. Now, we need to check the adjacent unvisited vertices of node 1. Node 1 is connected to nodes 0, 3, 2, 6, and 5. But node 0 is already visited and node 3 is already in the queue. Therefore, only nodes 2,6, and 5 will be inserted into the queue.
7. Node 3 was inserted into the queue after node 1, and according to FIFO rule, it qualifies to be removed from the queue and marked as “visited”.
8. Nodes 0, 1, 2, and 4 are adjacent vertices of node 3. But nodes 0 and 1 are visited and node 2 is already in the queue. Therefore only node 4 gets inserted into the queue.
9. Next, node 2 will be removed from the queue and marked as “visited”.
10. Nodes 1, 3, 4, and 5 are adjacent vertices of node 2. Since nodes 1 and 3 are already visited and nodes 4 and 5 are already in the queue, nothing has to be inserted into the queue. Therefore, the next element to be removed from the queue is node 6 and will be marked as “visited”.
11. Adjacent vertices of node 6 are nodes 1 and 4. Node 1 is already visited and node 4 is already in the queue. Nothing has to be inserted into the queue, so we move to the next node that can be removed from the queue.
12. The next node to be removed from the queue will be node 5 and will be marked as “visited”.
13. Adjacent vertices of node 5 are nodes 1 and 2. Since both nodes are visited, there is nothing to be inserted into the queue.
14. Finally, the only node remaining in the queue is node 4, which will be removed from the queue and marked as “visited”.

Now, that the queue is empty and it is the indication that we need to stop the BFS traversal.

We keep track of “visited” nodes so that they are not revisited!!! To do that, we remove the nodes from the queue and mark them as “visited”!!!

Once removed, the adjacent, unvisited vertices of that node are inserted into the queue. Note that any adjacent vertices of that node that are unvisited but already in the queue must not be inserted into the queue again!!!

The following diagram illustrates the status of the queue through BFS traversal!!!

status of queue

So, one valid Breadth-First-Search for the above graph is :

One valid traversal

There can be alternative valid traversals for the above graph depending on the order you insert the adjacent vertices of a node into the queue, e.g. initially, at node 0, if you choose to insert nodes 3 and 1 into the queue, in the order 3 and 1, then the traversal will be 0 3 1…so on!!!

Hope you understood Breadth-First-Search!!!

If you are interested, please check out my GitHub for the implementation of BFS and DFS!!!

Happy Learning!!!

References

1. https://www.youtube.com/watch?v=aMCI4AqVUug
2. https://www.youtube.com/watch?v=vf-cxgUXcMk