# A Simple Guide to Breadth First Search in JavaScript

## 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!

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:

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)          })     }).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          })     }).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)).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 codeRETURNS[['myhouse', 'inlaws'],['myhouse', 'momanddad']]`
`.map(edge => edge.filter(node => node != nodeName))`
`//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)`
`RETURNSadjacentNodes = [  { 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 discoveredRETURNS[  { 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']`

Written by

Written by

## Kelsey Shiba

#### Full Stack Software Engineer, Administrator, Designer, and Musician. 