A Simple Guide to Breadth First Search in JavaScript

Breadth First (Breath, first..) Search

Kelsey Shiba
Jan 3 · 7 min read

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:

Image for post
Image for post

Two helpful definitions

Vertices/Vertex: A point where two edges meet. In this case, a house.

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}

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?

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
})
}
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
})
}
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))
edges = [
['myhouse', 'momanddad'],
['momanddad', 'niece1'],
['momanddad', 'nephew'],
['myhouse', 'inlaws'],
['inlaws', 'kid2'],
['inlaws', 'kid1']
]
//after above line of code
RETURNS
[['myhouse', 'inlaws'],['myhouse', 'momanddad']]
.map(edge => edge.filter(node => node != nodeName)[0])
//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']
.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}
[{name: 'momanddad', distance: null, predecessor: null}, {name: 'inlaws', distance: null, predecessor: null}]
.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}]
function explored(node, adjacentNodes){
const current = node
adjacentNodes.forEach(node => {
node.distance = current.distance + 1
node.predecessor = current
})
return adjacentNodes
}
{name: 'myhouse', distance: null, predecessor: null}
[{name: 'momanddad', distance: null, predecessor: null}, {name: 'inlaws', distance: null, predecessor: null}]
[{  name: 'momanddad',
distance: 1,
predecessor: { name: 'myhouse', distance: null, predecessor: null }
},
{ name: 'inlaws',
distance: 1,
predecessor: { name: 'myhouse', distance: null, predecessor: null }
}]
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
}
{name: 'myhouse', distance: 0, predecessor: null}
let queue = [startingNode]//or more visually...queue = [{name: 'myhouse', distance: 0, predecessor: null}]
let discovered = [startingNode]
while(queue.length != 0){
let currentNode = queue.shift()
let adjacentNodes = explored(currentNode.name, vertices, edges)
RETURNS
adjacentNodes = [
{ name: 'momanddad', distance: null, predecessor: null },
{ name: 'inlaws', distance: null, predecessor: null }
]
discovered = discovered.concat(adjacentNodes);
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 }
}
]
queue = queue.concat(adjacentNodes)
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] }
}
]
bfs(startingNode, vertices, edges).map(node => node.name)
[
'myhouse',
'momanddad',
'inlaws',
'niece1',
'nephew',
'kid2',
'kid1'
]

JavaScript In Plain English

New JavaScript + Web Development articles every day.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store