# Breadth-First Search

## Course launching November 17, 2020

**Follow me on YouTube** for free coding interview videos.

Users who sign up for the email list will receive an exclusive 75% discount at launch.

- Find the shortest pathIt considers all the nodes closest first

- More memoryBFS typically requires more memory (commonly assumed)

Breadth-first search (BFS) traverses by checking the nodes closest to a parent before moving on.
BFS is used when we want to find the **shortest path** or **closest neighbors**.

BFS is implemented using a queue data structure. Because we access the items in FIFO order, we visit all the edges of a given node first and then progress onward.

BFS can be seen commonly in the real-world. For example, on Facebook we are recommended friends. What they do is create a graph of all the users and recommend the people closest to your friends since you are also more likely to be friends with them. The same thought process happens when Netflix recommends shows or Amazon recommends products - the closer the match is to you based on similar people, the more likely it's a fit.

To implement BFS, we will use a graph node that stores `data`

and its `edges`

.
The `edges`

variable is just an array of pointers to its sibling nodes.
We will also assume our graph is undirected.

Nodes will take the following form:

```
class GraphNode {
constructor(data) {
this.data = data;
this.edges = [];
}
}
```

We perform BFS iteratively by using a queue data structure.

```
const breadthFirstSearch = (startingNode) => {
const bfsQueue = [startingNode];
const visitedNodes = new Set();
visitedNodes.add(startingNode);
while(bfsQueue.length > 0) {
const node = bfsQueue.pop();
// Use node value for the question
visit(node);
node.edges.forEach(childNode => {
if (!visitedNodes.has(childNode)) {
bfsQueue.unshift(childNode);
visitedNodes.add(childNode);
}
});
}
}
```

Table of Contents