A quick explanation of DFS & BFS (Depth First Search & Breadth-First Search)

Introduction

So getting into the realm of data structures we encounter two concepts: Depth First Search and Breadth-First Search. The purpose of these two concepts is to explore data-sets, they both have different ways of approaching data-sets and I will try to cover them in this blog.

There are basically two steps that these algorithms do in all their cases: Visiting a vortex and exploring a vortex, vortex just meaning any element or node in the data-set. Visiting a vortex refers to the element that is currently being observed and exploring the vortex refers to observing if the currently visited vortex has other nodes attached to it.

BFS(Breadth-First Search)

So to better understand these algorithms we will use the following data-tree as an example.

In both BFS and DFS the first step is to pick a node or vortex to start our search, in this case, I will pick the number 2 at the top. BFS is very straight forward.

We first visit the vortex we chose(2) and we check to see if two has any children, we find out that 2 has 7 and 5 as children. So we would currently have the following order so far: 2, 7, 5. We then proceed to explore the first child vortex found which is 7. We can see that 7 has 3 children: 2, 10, and 6 so now our list would look like this: 2, 7, 5, 2, 10, and 6. Now we check if the second child(5) has children, we can see that 5 has 9 as a child so we would add nine to the list: 2, 7, 5, 2, 10, 6, and 9. We now repeat the same process for the first found children of 7 starting with 2 which has no children so we move to 10 that also has no children so we move to 6 and we find that 6 has 5 and 11 as children so we add them to the list: 7, 5, 2, 10, 6, 9, 5, and 11. Now we go back and check the child of 5 which is 9. We see that 9 has one child, 4 so we add it to the list: 7, 5, 2, 10, 6, 9, 5, 11, and 4. Now the next step is to go back to the number 6 and check to see if its children have more children and we see they have none so we go the number 4 and there is also no children so we are done.

So BFS is pretty easy right?! It is just like reading any text from left to right, in the simplest case, but in any given tree or data-set the procedure is the same.

DFS(Depth First Search)

To understand this algorithm I will use the same data-tree as an example.

As BFS we also have to pick an initial vortex to start our search so I will also pick the number 2 at the top. Now the difference between BFS and DFS is that DFS goes in a straight line, it doesn’t stop until the deepest part of a vortex is found hence the name “Depth-first search”. So let's go through each step that DFS takes to complete a search.

I selected the number 2 as my started point so the first step is to check if 2 has any children and we can see that it has 7. Here is were DFS is different than BFS, instead of checking to see if 2 has more children we stop and we continue with 7, we explore 7 and find out that 7 has 2 so we stop exploring 7 and we start exploring 2, 2 has nothing so we go back to 7 and we see that 7 has 10, 10 doesn't have anything so we go back to 7 and 7 also has 6. So far our list looks like this: 2, 7, 2, 10, and 6. So next we will explore 6 and find that 6 has 5 we stop exploring 6 and explore 5, we find that 5 doesn't have anything so we go back to 6 and find out that 6 has 11 so we explore 11 we find nothing so now we go back to the first 2 again and our list looks like this now: 2, 7, 2, 10, 6, 5, and 11.

We now explore 2 again and see that it has another child, 5, so we stop exploring 2 and we explore 5 and we find that 5 has 9 so we explore 9 and 9 has 4, we explore 4 and find that 4 doesn’t have anything so we go back until we reach 2 because there are no more children. We explore 2 again and find that 2 has no more children so we are finished, and our final list looks like this: 2, 7, 2, 10, 6, 5, 11, 5, 9, and 4.

Conclusion

So we in this blog we saw what BFS and DFS is and their differences, thank you for reading and I hope this blog helped you understand better these two concepts.