# A Simple Guide to Breadth First Search in JavaScript

## Breadth First (Breath, first..) Search

## You know how they say: “i*f 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*