# Efficient Graph Search

*Note: This was originally published as an Observable notebook.*

Many textbook implementations of breadth-first search contain a flaw: they are needlessly slow.

Terence Kelly's Drill Bits article describes the flaw and how to fix it.

Itβs fun to see how this plays out visually, so here are a few pictures of the problem and how it can be solved.

First, let's take a look at a textbook BFS implementation. The code below is adapted from *Algorithms* by Dasgupta, Papadimitriou, and Vazirani:

```
function bfs(G, s) {
// For all vertices `v` reachable from `s`, dist[v] is set
// to the distance from `s` to `v`.
const V = G.numVertices; // Assume the number of vertices is known
let dist = new Array(V).fill(Infinity); // Init distances to β
dist[s] = 0; // Init the source distance to zero
let Q = [s]; // Init a queue containing just s
while (Q.length > 0) { // While the queue is nonempty:
let u = Q.shift(); // Pop the next vertex from the queue
for (let v of G.neighbors[u]) { // For all edges (u, v):
if (dist[v] == Infinity) { // If we haven't seen v before:
dist[v] = dist[u] + 1; // Set its distance
Q.push(v); // Push v onto the queue
}
}
}
return dist;
}
```

This algorithm is correct, but in some cases does extra work proportional to the number of vertices squared.

We can see the issue by looking at how this algorithm processes a complete graph, which has an edge between every pair of vertices.

BFS on a complete graph starts at a source vertex and immediately visits all of the others, since each is just one hop away.

Once those vertices has been visited, *all of the useful work is done* β we now know the distance to every vertex from the source. But the textbook BFS is far from finished!

Slide the slider below to watch the textbook algorithm play out.

The

By the

But because the neighbors of the first vertex were all enqueued, the algorithm proceeds to visit them, along with *their* neighbors, which results in the inspection of

Fortunately, we can fix this with just a few lines of code:

```
function bfsImproved(G, s) {
const V = G.numVertices; // Assume the number of vertices is known
let dist = new Array(V).fill(Infinity); // Init distances to β
dist[s] = 0; // Init the source distance to zero
let Q = [s]; // Init a queue containing just s
let f = 1; // π Initialize the number of seen vertices
while (Q.length > 0) { // While the queue is not empty:
let u = Q.shift(); // Pop the next vertex from the queue
for (let v of G.neighbors[u]) { // For all edges (u, v):
if (dist[v] == Infinity) { // If we haven't seen v before:
dist[v] = dist[u] + 1; // Set its distance
if (++f == V) return dist; // π Return if we've seen all V vertices
Q.push(v); // Push v onto the queue
}
}
}
return dist;
}
```

The added code tracks the number of vertices that have been found and finalized, and returns as soon as we've seen them all..

In the case of our complete graph this simple check takes the total number of steps down from

We can get a visceral sense for the amount of extra work by laying out all of the steps side-by-side.

The improved algorithm is finished by step

The textbook algorithm continues on, churning through

Hopefully this primes your intuition for the problem and its solution. If youβd like to learn more, go read Terence Kelly's article.