Breadth first search is a search algorithm used for searching graphs. It will search all of the closest nodes, then the following closest nodes. The data structure used to implement this algorithm is a *queue*. Recall, queues use a first-in-first out principle, which is how we will traverse each of the closest nodes first.

For the sake of this example, this is the interface of a node.

```
interface Node {
key: string;
value: any;
children: Node[] | null;
}
```

To start, we can write our function signature.

```
function breadthFirstSearch(start, visitFn) {}
```

We take in two params;

`start`

- the node where we want to start our search from.`visitFn`

- a callback that is called every time we visit a node.

First, we will implement our queue. We can use an array in javascript as a queue. The queue should start off with the `start`

node, so that we have a starting point.

We will also keep track of the nodes we have visited with an `visited`

map. We need to do this because some edges may point to a node we already visited, and we only want to visit a node once.

```
function breadthFirstSearch(start, visitFn) {
let queue = [start];
let visited = {};
}
```

To start our search, we will use a `while`

loop. We want to search through all the nodes until the queue is empty. When the queue is empty, we know we have visited every node.

```
function breadthFirstSearch(start, visitFn) {
let queue = [start];
let visited = {};
while (queue.length) {}
}
```

In our loop, we dequeue the first node out of the queue. Recall, queues are first-in-first-out, so the first node we added to the queue will be pulled out. We can use the .shift() method on our array implementation of a queue to get the node at index `0`

.

```
function breadthFirstSearch(start, visitFn) {
let queue = [start];
let visited = {};
while (queue.length) {
const current = queue.shift();
}
}
```

Next, we check if we have already have visited this node. If we have, we can move on to the next iteration by using continue.

```
function breadthFirstSearch(start, visitFn) {
let queue = [start];
let visited = {};
while (queue.length) {
const current = queue.shift();
if (visited[current.key]) continue;
}
}
```

If we haven’t visited the node, then we need to visit it! We call the visitFn with the node, and add the node’s key to the visited map.

```
function breadthFirstSearch(start, visitFn) {
let queue = [start];
let visited = {};
while (queue.length) {
const current = queue.shift();
if (visited[current.key]) continue;
visitFn(current);
visited[current.key] = true;
}
}
```

Before finishing this iteration, we need to see if the `current`

node has any children. If it does, we will add each child to the queue. To accomplish this, we can use a for loop to add each child to the queue.

```
function breadthFirstSearch(start, visitFn) {
let queue = [start];
let visited = {};
while (queue.length) {
const current = queue.shift();
if (visited[current.key]) continue;
visitFn(current);
visited[current.key] = true;
for (let child of current.children) {
queue.push(child);
}
}
}
```

Great, we have implemented a breadth first search in JavaScript. Here is the final result with annotations.

```
/**
* start - Node where we start our search from.
* visitFn - A callback called with each Node we visit.
*/
function breadthFirstSearch(start, visitFn) {
// Create a queue, and add the first (start) node to it as a starting point.
let queue = [start];
// Create a map of nodes we have visited, so that we don't visit a node twice.
let visited = {};
// While the queue isn't empty...
while (queue.length) {
// Get the current node by shifting the node at 0 off the array.
const current = queue.shift();
// Check if we have already visited this node. If we have, skip this loop.
if (visited[current.key]) continue;
// If we get here, we haven't visited this node. Visit it!
visitFn(current);
// Add it's key to the visited map so we don't visit it again.
visited[current.key] = true;
// Add any of the current node's children to our queue to visit later.
for (let child of current.children) {
queue.push(child);
}
}
}
```