Write a Depth First Search Algorithm for Graphs in JavaScript

Instructor: [00:00] As the name implies, depth first search is a graph search algorithm that explores as far as it can down a particular path before climbing back up and working down another one. We'll add a depth first search method to our graph object.

[00:14] This method will receive two arguments, a starting node key to find which node in the graph to start the search from and a visiting function to be called as we visit each node for the first time. First, we need to get the starting node by using the get node method.

[00:30] Next, we need to keep track of which nodes we have visited and which ones we haven't. There are several ways we can do this, but I'm going to do it by keeping a visited object where each key corresponds with a node's key, and the value starts as false. Now, depth first search involves a recursive algorithm.

[00:49] Essentially, if there's another level to go down, we need to explore that one until we reach a dead end. I'm going to create an explore function that we will call on our nodes. If we visited this node, then return from the function immediately.

[01:04] Otherwise, call the visiting function on the node and mark it as visited. Next, we want to loop through each of this node's neighbors and call explore on them. Lastly, we start our algorithm by calling explore on our starting node. Now that we've created our depth first search algorithm, let's use it.

[01:24] I've pre-made a graph that I'll copy paste into the file that looks like this. I want to call depth first search on our graph starting at node A and logging out each key as we go. If I bring the graph back onto the screen and we call our search in the terminal, we could see that we went as far down the path of A we could before we climbed back up and went down another path.