Algorithms in JavaScript
Implement a Breadth-first Search Function in JavaScript
The breadth-first search is a different kind of search algorithm because it is run against graphs. It is typically used to answer one or both questions, is there a path between point A and point B? As well as, what is the shortest path from point A to point B. It utilizes a queue which is a first in first out data structure. Let’s implement a Breadth-first search function in JavaScript!
Instructor: [00:00] Let's say we needed to write a program that searched through my Facebook friends, looking for the closest friend that owned a dog. We want to first search through my immediate set of friends before moving on and searching through the friends of my friends. Remember, the goal was to find the closest friend relationship that owns a dog.
[00:16] Before we search through Henry's friend of a friend, we need to check John's immediate set of friends first. Looking over the information we have so far, I've got three friends, Henry, John, and Amy. Henry has two friends, Peggy and Kelly. John has a friend of Kelly, so Henry and John share the same friend. Amy doesn't have any friends.
[00:37] Peggy, who is Henry's friend, doesn't have any friends. Kelly, who is shared between Henry and John, have one friend named Claire. In order to solve this problem, we need to structure our data in the form of a graph and use the breadth first search algorithm.
[00:52] This isn't a graph that uses a X and Y axis. Graphs is made up of nodes and edges. In our example, the people are the nodes and the relationship between each friend are the edges. Imagine all of these relationships are connected by arrows or the edges.
[01:09] Now let's write const graph equals an empty object. Then we'll say, graph Tyler equals an array of friends. Graph Henry equals an array of friends. John with his friends. Amy doesn't have any friends so she'll be an empty array. Same with Peggy. Kelly has one friend of Claire and Claire doesn't have any friends, so she'll be an empty array as well.
[01:33] Perfect. This is how we can graph our data together. We've flattened out all the nodes or people into this object and assigned their value as an array of objects that show their friends and if they have a dog or not.
[01:47] In order to find the shortest path person that owns a dog, we need to work with a queue data structure. Queues work exactly as they do in real life. Unlike in recursion, where it's first in last out, queues are first in first out. They work the same as stacks. You can't access random elements in the queue. Instead, there are only two operations, N queue and D queue.
[02:10] Let's go ahead and create our breadth first search function. This function is going to take a name. The first thing we'll do is create our queue data structure. We'll say, let search queue equals as an array dot concat graph at name. Next, we'll create an array of all the search individuals and we'll say while our search queue has something in it, so dot length, we're going to loop over each one.
[02:32] We'll say, let person equals search queue dot shift to grab the first one in the queue. If our person that we pulled from the queue is not already in our searched array, then we can check to see if this person has a dog.
[02:48] If they do have a dog, then we found a person and we're going to return a string that says, this person has a dog. If not, then we're going to concat their friends onto the back of our search queue. Do a dot concat, graph at this person's ID.
[03:07] Then we're going to push this person into our searched array so we don't go through them again later. If not, at the end we're going to return a string that says there are no friends that have a dog. With this in place, let's do a console log with our search function, passing through my name so we begin with Tyler. Perfect. It looks like Claire has a dog.
[03:27] Before we go back and look at our graph data, let's go through this function one more time. The first thing we did was create a queue using an array. We added all of my immediate friends into the queue, so we began working with Henry, John, and Amy. When we get to the while loop, we have three items in our queue we need to look over.
[03:45] The shift mutates our array or queue by taking the first item out and returns it. Person is being reassigned within each loop with the first object in our queue while also removing them from the queue. In order to avoid cycles, we check to see if we have already checked this person by looking through our searched array to see if they're in there.
[04:08] If our person has a dog, then we return this string. If not, then we need to concat or push this person's friends onto the back of our current queue. Then push them into our searched queue, which again helps us avoid cycles. If no friends have dogs, then we return this string.
[04:28] We know that Claire is three levels deep, so if our function is working properly, if we were to change Peggy to have a dog, our function should return Peggy because it's my friend, Henry's friend. We see that Peggy is returned from our function before Claire. If nobody has a dog, Claire doesn't, neither does Peggy, then we should return there are no friends that have a dog.
Poor Aimee...
I implemented it using only one Queue and do not have to maintain another array. Could you guys please have a look. it's working correctly from my side:
const search = (name, bfs = true) => {
const friends = graph[name];
console.log(friends);
let searched = [].concat(friends);
console.log(searched)
while (searched.length > 0) {
const person = searched.shift();
console.log(person);
if (person.dog) {
return `${person.id} has a dog`
}
else {
const personsFriends = graph[person.id];
console.log(personsFriends)
if (bfs) {
searched = searched.concat(personsFriends);
} else {
searched = personsFriends.concat(searched)
}
console.log(searched)
}
}
return `no one has a dog`
}
console.log(search("tyler"))
This is best explanation that i've ever come across. Thank you so much @tyler.