Breadth First JavaScript Search Algorithm for Graphs
Breadth first search is a graph search algorithm that starts at one node and visits neighboring nodes as widely as possible before going further down any other path. This algorithm requires the use of a queue to keep track of which nodes to visit, so it might be worth your time to brush up on that data structure before watching this lesson.
Instructor: [00:00] As the name implies, breadth-first search is a graph search algorithm that starts at one node and explores as widely as possible before going further down adjacent nodes. We'll add a breadth-first search method to our graph object.
[00:15] We want to accept two arguments, a starting node key to find which node in our graph to start from and a visit function to call when we visit each node. The first thing we need to do is get the starting node using the getNode 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. I'm going to do it through using an object.
[00:40] I'm going to reduce our nodes down to an object where each key is the current node's key and the value is set to false, that I can set to true later on when we've visited that corresponding node.
[00:52] Next, we'll need to keep track, in order, which nodes that we need to visit. We'll use a createQueue function I've imported from another lesson. The first node we need to visit is our starting node, so we'll enqueue it.
[01:06] Now, while the queue is not empty, we want to perform our search algorithm. Part of our algorithm will enqueue more nodes. This will continue to go on until we've visited every node in our graph.
[01:18] Each time we run through this loop, we want to dequeue the first item out of our queue and set that as the current node. If we haven't visited this node before, we need to call our visit function on it and set its corresponding value to true in our visited hash.
[01:37] Now, we want to loop through each neighbor of our current node. If we haven't visited before, we want to add it to our queue. Now that we've implemented breadth-first search, let's try it out on a graph.
[01:52] I've premade a graph for us that I'll copy-paste the code into our file. It looks like this. I want to use breadth-first search to print out the node keys as arrive at each one, into the console.
[02:05] I'll start from node A. If I bring the graph back onto the screen and we compare it to the result in the terminal, we can see how we branched out from node A and visited all of its neighbors before proceeding down node B's neighbors.
In the transcript, in the second example, an object named visited is created. In later examples, it is referenced as visitedHash. This is corrected in the full source code above.
Thanks for this Rob and Christopher! I got the transcripts updated.
If you're not using the code in the code sandbox and don't want to import the queue data structure from the previous lesson you can also just use an array to store the nodes. Also, the transcript has some discrepancies with the usage of visited and visitedHash for the name of the aforementioned queue.