A Simple Guide to Breadth First Search in JavaScript
Breadth First (Breath, first..) Search
You know how they say: “if you can teach it, then you really know what you’re talking about?”
Well, let’s just say that’s what I’m trying to do today. So — edits and comments very welcome!
Breadth First Search
If you have not run into it already — breadth first search is an algorithm that visits nodes in a specific order — first the root node, then it’s adjacent nodes. In other words, if I have two neighbors on each side, I’d start with my house, then visit my right-and-left neighbor simultaneously — then continue that trend with my neighbors’ neighbors. I need a visual for that, so I made one:
I know — crazy neighborhood right?! Let’s jump into it so we can get on with our lives.
Two helpful definitions
Vertices/Vertex: A point where two edges meet. In this case, a house.
Edges/Edge: The connection — two vertices that are connected. The two houses that create the path between each other.
In Code:
edges = [
['myhouse', 'momanddad'],
['momanddad', 'niece1'],
['momanddad', 'nephew'],
['myhouse', 'inlaws'],
['inlaws', 'kid2'],
['inlaws', 'kid1']
]vertices = [
{name: 'myhouse', distance: null, predecessor: null},
{name: 'momanddad', distance: null, predecessor: null},
{name: 'inlaws', distance: null, predecessor: null},
{name: 'niece1', distance: null, predecessor: null},
{name: 'nephew', distance: null, predecessor: null},
{name: 'kid1', distance: null, predecessor: null},
{name: 'kid2', distance: null, predecessor: null}
]
Find a Node
In many of these algorithms, it is helpful to be able to find a node — so let’s write code for that.
function findNode(nodeName, vertices){
return vertices.find(vertex=> vertex.name == nodeName)
}In Action:
findNode('myhouse', vertices)RETURNS the vertex OBJECT if found.
{name: 'myhouse', distance: null, predecessor: null}
Distance: As you can see in the vertices list — in order for us to have a structure, we need to keep track of the distance between 2 nodes. For our root node the distance is 0. For the two adjacent nodes, the distance is 1, as they are 1 away from the root node.
Predecessor: Another way to track inside of this algorithm is to log the predecessor. When exploring the neighbors houses, MY house becomes their predecessor.
Two Actions on a Node in BFS
There are two actions one would take on a node in BFS. One is to visit a node. The other is to explore a node, which means figuring out what its adjacent nodes are. Sticking with my house analogy, I can visit my house, but if I explore it — I find out that I have two neighbors! — My mom and dad and my in-laws. Sounds like a fun neighborhood huh?
We know how to visit/find a node, let us explore a node by returning its adjacent nodes. Let’s do that in code, and then let’s break that down and boil it.
function findAdjacent(nodeName, vertices, edges) {
return edges.filter(function(edge){
return edge.includes(nodeName)
}).map(function(edge) {
return edge.filter(function(node){
return (node !=nodeName)
})[0]
}).map(function(name){
return findNode(name, vertices)
}).filter(function(node){
return node.distance == null
})
}I don’t know about you, but this solution confused me because I’m a visual learner. First, let’s re-write it, and then we can break it down. Here’s another way of doing it with arrow functions.
function findAdjacent(nodeName, vertices, edges){
return edges.filter(edge => {
return edge.includes(nodeName)
}).map(edge => {
return edge.filter(node => {
return node != nodeName
})[0]
}).map(name => {
return findNode(name, vertices)
}).filter(node => {
return node.distance == null
})
}And boiled down again with ES6 arrow function and implicit return (if it helps you)
function findAdjacent(nodeName, vertices, edges){
return edges.filter(edge => edge.includes(nodeName)).map(edge => edge.filter(node =>
node != nodeName)[0]).map(name =>
findNode(name, vertices)).filter(node =>
node.distance == null)
}Break Down
Let’s break this down step-by-step. I like talking thru these replace all the arrows with the words “if the(y)/these/those”.
return edges.filter(edge => edge.includes(nodeName))^ return all the edges (which are two sets of anchor points in an array) if those two points includes the nodeName, which we have set to a string of ‘myhouse’ currently. Remember that the filter iterator auto-returns an ARRAY, so here’s what we are working with at this point.
edges = [
['myhouse', 'momanddad'],
['momanddad', 'niece1'],
['momanddad', 'nephew'],
['myhouse', 'inlaws'],
['inlaws', 'kid2'],
['inlaws', 'kid1']
]//after above line of code
RETURNS
[['myhouse', 'inlaws'],['myhouse', 'momanddad']]
Then, take that return value, and MAP it
.map(edge => edge.filter(node => node != nodeName)[0])Go thru each set of edges, take each node and filter them if the node does NOT equal the given node name.
//examine each set
['myhouse', 'momanddad']
['myhouse', 'inlaws']
//filter that array for nodes if it DOES NOT MATCH, therefore we are left with an array of:RETURNS
['inlaws', 'momanddad']
Now to MAP this array, this time returning the OBJECT node for each of the items in the array.
.map(name => findNode(name, vertices))Goes thru
'inlaws'performs findNode on it ('inlaws', vertices)
RETURNS from the vertices list
{name: 'inlaws', distance: null, predecessor: null}Moves to
'momanddad'
RETURNS
{name: 'momanddad', distance: null, predecessor: null}
Remember that MAP returns an array, so our actual return looks like this:
[{name: 'momanddad', distance: null, predecessor: null}, {name: 'inlaws', distance: null, predecessor: null}]Finally, filter that array if the node.distance is null. This means that the node has not been EXPLORED yet. Once the node is explored, we will add distance to it. More on that later.
.filter(node => node.distance == null})So we filter this array to ensure that all the distances are null. They are indeed NULL --
RETURNS
[{name: 'momanddad', distance: null, predecessor: null}, {name: 'inlaws', distance: null, predecessor: null}]
Explore — Mark the Distance and Predecessor
Now we need a way to know that a node(s) has been explored. So we need a method that marks the distance from the previous node and makes the previous node the predecessor.
function explored(node, adjacentNodes){
const current = node
adjacentNodes.forEach(node => {
node.distance = current.distance + 1
node.predecessor = current
})
return adjacentNodes
}It’s important to note here what we are passing in here as arguments to this function. In this case — “node” is an entire object that looks like this:
{name: 'myhouse', distance: null, predecessor: null}The adjacentNodes look like the return value from the findAdjacent function.
[{name: 'momanddad', distance: null, predecessor: null}, {name: 'inlaws', distance: null, predecessor: null}]After we execute the function explored, here is the return value:
[{ name: 'momanddad',
distance: 1,
predecessor: { name: 'myhouse', distance: null, predecessor: null }
},
{ name: 'inlaws',
distance: 1,
predecessor: { name: 'myhouse', distance: null, predecessor: null }
}]The Breadth First Search Algorithm
function bfs(startingNode, vertices, edges){
startingNode.distance = 0
let queue = [startingNode]
let discovered = [startingNode]
while(queue.length != 0){
let currentNode = queue.shift()
let adjacentNodes = findAdjacent(currentNode.name, vertices, edges)
discovered = discovered.concat(adjacentNodes);
explored(currentNode, adjacentNodes)
queue = queue.concat(adjacentNodes)
} return discovered
}
OK. Let’s deconstruct this.
First, let’s set the startingNode.distance to 0, so we are not trying to add 1 to null in our explored method. Pretty straight forward, but here’s the new root node object:
{name: 'myhouse', distance: 0, predecessor: null}Then, we create a queue so we know what node we are going to explore next. We create the queue with the startingNode.
let queue = [startingNode]//or more visually...queue = [{name: 'myhouse', distance: 0, predecessor: null}]
Then create a discovered array or the one used to print out the nodes in order of discovery, which looks identical to the queue.
let discovered = [startingNode]Begin the loop, based on the length of the queue:
while(queue.length != 0){Set the currentNode to the FIRST one in the queue.
let currentNode = queue.shift()Explore the adjacent nodes of that current node (a.k.a add distance and predecessor)
let adjacentNodes = explored(currentNode.name, vertices, edges)Note that this returns and ARRAY of OBJECTS.
RETURNS
adjacentNodes = [
{ name: 'momanddad', distance: null, predecessor: null },
{ name: 'inlaws', distance: null, predecessor: null }
]The we add them to our list of discovered nodes that will print.
discovered = discovered.concat(adjacentNodes);And mark that the’ve been explored.
explored(currentNode, adjacentNodes)RETURNS
[
{
name: 'momanddad',
distance: 1,
predecessor: { name: 'myhouse', distance: 0, predecessor: null }
},
{
name: 'inlaws',
distance: 1,
predecessor: { name: 'myhouse', distance: 0, predecessor: null }
}
]
Add the adjacent nodes to the queue so they can be explored for their adjacent nodes (niece, nephew1, kid1, kid2)
queue = queue.concat(adjacentNodes)Finally, return the list in order.
return discovered
RETURNS
[
{ name: 'myhouse', distance: 0, predecessor: null },
{
name: 'momanddad',
distance: 1,
predecessor: { name: 'myhouse', distance: 0, predecessor: null }
},
{
name: 'inlaws',
distance: 1,
predecessor: { name: 'myhouse', distance: 0, predecessor: null }
},
{
name: 'niece1',
distance: 2,
predecessor: { name: 'momanddad', distance: 1, predecessor: [Object] }
},
{
name: 'nephew',
distance: 2,
predecessor: { name: 'momanddad', distance: 1, predecessor: [Object] }
},
{
name: 'kid2',
distance: 2,
predecessor: { name: 'inlaws', distance: 1, predecessor: [Object] }
},
{
name: 'kid1',
distance: 2,
predecessor: { name: 'inlaws', distance: 1, predecessor: [Object] }
}
]For a simpler print out, you can always do this:
bfs(startingNode, vertices, edges).map(node => node.name)Which shall return:
[
'myhouse',
'momanddad',
'inlaws',
'niece1',
'nephew',
'kid2',
'kid1'
]That’s it! Now take a deep breadth. I mean breath. And I wouldn’t recommend living that close to your family, unless you “node” what you’re doing. Yep, I went there.
Code On! ~ Kelsey
Code Credit & Licensing Information: https://github.com/learn-co-students/bfs-lab-g-416
