Graph Traversal — Breadth-First Search vs Depth-First Search (Pt 2)

In my last article on Breadth-First Search and Depth-First Search I explained both types of graph traversal and talked a bit about the pros and cons of each. In this article, I will focus on how we can implement each type of algorithm using JavaScript!

First, lets quickly reiterate what was explained in the last article.

Breadth-First Search(BFS)

A graph traversal algorithm that traverses the graph one level at a time. It visits all the children of the parent, then visits all the grandchildren, and so on.

BFS

Depth-First Search(DFS)

A graph traversal algorithm that visits the first child node of the parent, then goes on to visit the first grandchild and so on.

DFS

Again, feel free to check out my most recent article if you’re a little confused. It goes into these graph traversal algorithms a little deeper, and also explains a few ways to better organize the structure of a graph and its children!

Now that we have a deeper understanding of graphs, BFS, and DFS, lets write some code!

First, we must write a function that allows us to create the nodes in our graphs:

node creation function

As you can see above, I’ve written a function that takes a value as an argument. The function returns two things, the value passed in, and an empty array where we will store that values children.

Now that we’ve got our function, lets create some nodes!

created nodes

Here we’ve created a total of 15 nodes, all return the value passed in(a letter), and all have an empty array of children within them. we can console.log any of these newly created variables to see its value and its children.

Now that we’ve got our nodes, we’ll want to give them some children. The children will be other nodes we’ve created. For example, A will be at the top of our graph with the children B, C, and D. Then we will give B, C, and D their children, and so on.

Nodes with children

Here is the graph we’ve created:

Graph

Pretty cool!

Now that our nodes have children, we can console.log each node and see its children, from there we can even see the grandchildren of the node we’ve logged.

We can also ‘console.table({a,b,c,d,e,f,g,h,i,j,k,l,m,n,o})’ all of our nodes to get a pretty decent visualization in our console, and also to make sure our nodes have the correct amount of children. If you run the console.table function I’ve written above, you should see this in your console.

OK

Enough of the setup, lets get down to business.

Breadth-First Search

what we’ll want to accomplish in this function is:

1. create a queue, starting with a node that we are going to pass into the function.
2. take the first node in the queue, perform a callback function on it, and push that nodes children into the queue, deleting the node we just performed a callback on in the process.
3. repeat the process until there are no more nodes left in the queue.

Breadth-First Search

So, we’ve defined a function that takes two arguments, the starting node, and a callback.

First, we put the starting node into the queue.

Second, we made sure to perform our search while there are still items left in the queue.

Third, we took that first item in the queue, deleted it from the queue, performed our callback function on it, then pushed its children to the queue.

This function will repeat itself until there are no more nodes left in the queue to search for!

We can make sure this function is working in our console.

Run ‘bfs(a, console.log)’

We should see all of our nodes console.logged in alphabetical order! If you take another look at the graph above, you will notice that this is exactly how a BFS traversal should work in our situation. Hooray!!!

If you choose to have a different starting node, you will only be traversing that node and its children. This function does not go up the graph only down.

Depth-First Search

First, we must realize there are actually two ways to accomplish a DFS algorithm:

1. Depth-First Pre Order
2. Depth-First Post Order

Depth-First Pre Order

In this version of our DFS algorithm, we go down each child node one level at a time. So for our example in the graph above, the order in which we traverse our tree will be:

A->B->E->K->F->C->G->L->M->D->H->I->N->O->J

Now, lets write our function!

What we’ll want to accomplish in this function is:

1. perform our callback on our starting node that we pass into the function.
2. iterate through the starting nodes children, and perform the same function on its first child, then again on the first grandchild, and so on until there are no more children in that string of nodes
3. The function should then traverse up one level, and see if there are any other children to perform the callback on
4. The function then repeats itself until it has visited all the children in the graph

DFS Pre Order

So we’ve defined our function, again taking a starting node and a callback

First, we perform the callback on the starting node

Second, we iterate through the starting nodes children and perform call the dfsPreOrder function again, repeating the process, only now the starting node is the original starting nodes first child.

Congrats! You’ve successfully traversed the graph using the Depth-First Search algorithm!

Now, lets perform our DFS in the Post Order version.

Depth-First Post Order

In this version of the DFS we want to go all the way to the bottom of our graph first, then work our way up from there. Again, using the graph example I showed above, the order in which we should be traversing this graph will be:

K->E->F->B->L->M->G->C->H->N->O->I->J->D->A

Lets write it out!

We’ll want to do that same as our DFS post order, except go all the way down to bottom of our graph first then work our way up.

DFS Pos Order

As you can see, this function is basically the same as our DFS Pre Order algorithm. The only difference is we iterate through the starting nodes children, then call the dfsPostOrder function on each node until we are all the way at the bottom, then we invoke our callback function on the deepest node, and the algorithm works its way up from there!

I hope you enjoyed this walkthrough on writing functions to perform Depth-First search and Breadth-First Search algorithms using JavaScript! As I mentioned in my last article, the understanding of algorithms in programming is extremely important and shows that you understand the fundamentals of programming. I aim to learn more algorithms along my software engineering journey, and I hope you do too!