The breadth-first search algorithm

Breadth-first search assigns two values to each vertex $v$:

• A distance, giving the minimum number of edges in any path from the source vertex to vertex $v$.

• The predecessor vertex of $v$ along some shortest path from the source vertex. The source vertex's predecessor is some special value, such as null, indicating that it has no predecessor.

If there is no path from the source vertex to vertex $v$, then $v$'s distance is infinite and its predecessor has the same special value as the source's predecessor.

For example, here's an undirected graph with eight vertices, numbered 0 to 7, with vertex numbers appearing above or below the vertices. Inside each vertex are two numbers: its distance from the source, which is vertex 3, followed by its predecessor on a shortest path from vertex 3. A dash indicates null:

In BFS, we initially set the distance and predecessor of each vertex to the special value (null). We start the search at the source and assign it a distance of 0. Then we visit all the neighbors of the source and give each neighbor a distance of 1 and set its predecessor to be the source. Then we visit all the neighbors of the vertices whose distance is 1 and that have not been visited before, and we give each of these vertices a distance of 2 and set its predecessor to be vertex from which we visited it. We keep going until all vertices reachable from the source vertex have been visited, always visiting all vertices at distance $k$ from the source before visiting any vertex at distance $k+1$.

Given the example above, here are the steps plus a visualization to play through each step:

• Start by visiting vertex 3, the source, setting its distance to 0.

• Then visit vertices 2 and 6, setting their distance to 1 and their predecessor to vertex 3.

• Start visiting from vertices at distance 1 from the source, beginning with vertex 2. From vertex 2, visit vertices 4 and 5, setting their distance to 2 and their predecessor to vertex 2. Don't visit vertex 3, because it has already been visited.

• From vertex 6, don't visit vertex 5, because it was just visited from vertex 2, and don't visit vertex 3, either.

• Now start visiting from vertices at distance 2 from the source. Start by visiting from vertex 4. Vertex 2 has already been visited. Visit vertex 1, setting its distance to 3 and its predecessor to vertex 4.

• From vertex 5, don't visit any of its neighbors, because they have all been visited.

• Now start visiting from vertices at distance 3 from the source. The only such vertex is vertex 1. Its neighbors, vertices 4 and 5, have already been visited. But vertex 0 has not. Visit vertex 0, setting its distance to 4 and its predecessor to vertex 1.

• Now start visiting from vertices at distance 4 from the source. That's just vertex 0, and its neighbor, vertex 1, has already been visited. We're done!

Notice that because there is no path from vertex 3 to vertex 7, the search never visits vertex 7. Its distance and predecessor remain unchanged from their initial values of null.

A couple of questions come up. One is how to determine whether a vertex has been visited already. That's easy: a vertex's distance is null until it has been visited, at which time it gets a numeric value for its distance. Therefore, when we examine the neighbors of a vertex, we visit only the neighbors whose distance is currently null.

The other question is how to keep track of which vertices have already been visited but have not yet been visited from. We use a queue, which is a data structure that allows us to insert and remove items, where the item removed is always the one that has been in the queue the longest. We call this behavior first in, first out. A queue has three operations:

• enqueue(obj) inserts an object into the queue.

• dequeue() removes from the queue the object that has been in it the longest, returning this object.

• isEmpty() returns true if the queue currently contains no objects, and false if the queue contains at least one object.

Whenever we first visit any vertex, we enqueue it. At the start, we enqueue the source vertex because that's always the first vertex we visit. To decide which vertex to visit next, we choose the vertex that has been in the queue the longest and remove it from the queue—in other words, we use the vertex that's returned from dequeue(). Given our example graph, here's what the queue looks like for each step, plus the previous visualization shown with the queue state:

• Initially, the queue contains just vertex 3 with distance 0.

• Dequeue vertex 3, and enqueue vertices 2 and 6, both with distance 1. The queue now contains vertex 2 with distance 1 and vertex 6 with distance 1.

• Dequeue vertex 2, and enqueue vertices 4 and 5, both with distance 2. The queue now contains vertex 6 with distance 1, vertex 4 with distance 2, and vertex 5 with distance 2.

• Dequeue vertex 6, and don't enqueue any vertices. The queue now contains vertex 4 with distance 2 and vertex 5 with distance 2.

• Dequeue vertex 4, and enqueue vertex 1 with distance 3. The queue now contains vertex 5 with distance 2 and vertex 1 with distance 3.

• Dequeue vertex 5, and don't enqueue any vertices. The queue now contains just vertex 1 with distance 3.

• Dequeue vertex 1, and enqueue vertex 0 with distance 4. The queue now contains just vertex 0 with distance 4.

• Dequeue vertex 0, and don't enqueue any vertices. The queue is now empty. Because the queue is empty, breadth-first search terminates.

Notice that at each moment, the queue either contains vertices all with the same distance, or it contains vertices with distance $k$ followed by vertices with distance $k+1$. That's how we ensure that we visit all vertices at distance $k$ before visiting any vertices at distance $k+1$.

Implement breadth-first search

/* A Queue object for queue-like functionality over JavaScript arrays. */
var Queue = function() {
    this.items = [];
};
Queue.prototype.enqueue = function(obj) {
    this.items.push(obj);
};
Queue.prototype.dequeue = function() {
    return this.items.shift();
};
Queue.prototype.isEmpty = function() {
    return this.items.length === 0;
};

/*
 * Performs a breadth-first search on a graph
 * @param {array} graph - Graph, represented as adjacency lists.
 * @param {number} source - The index of the source vertex.
 * @returns {array} Array of objects describing each vertex, like
 *     [{distance: _, predecessor: _ }]
 */
var doBFS = function(graph, source) {
    var bfsInfo = [];

    for (var i = 0; i < graph.length; i++) {
	    bfsInfo[i] = {
	        distance: null,
	        predecessor: null };
    }

    bfsInfo[source].distance = 0;

    var queue = new Queue();
    queue.enqueue(source);

    // Traverse the graph
    
    // As long as the queue is not empty:
    //  Repeatedly dequeue a vertex u from the queue.
    //  
    //  For each neighbor v of u that has not been visited:
    //     Set distance to 1 greater than u's distance
    //     Set predecessor to u
    //     Enqueue v
    //
    //  Hint:
    //  use graph to get the neighbors,
    //  use bfsInfo for distances and predecessors 
    while (!queue.isEmpty()) {
        var ... = queue.dequeue();

        for (...; ...; ...) {
	        var ... = graph[...][...];

	        if (bfsInfo[...].... === ...) {
	            ...;
	            ...;
	            ...;
	        }
        }
    }
    return bfsInfo;
};


var adjList = [
    [1],
    [0, 4, 5],
    [3, 4, 5],
    [2, 6],
    [1, 2],
    [1, 2, 6],
    [3, 5],
    []
    ];
var bfsInfo = doBFS(adjList, 3);
for (var i = 0; i < adjList.length; i++) {
    println("vertex " + i + ": distance = " + bfsInfo[i].distance + ", predecessor = " + bfsInfo[i].predecessor);
}

/*
Program.assertEqual(bfsInfo[0], {distance: 4, predecessor: 1});
Program.assertEqual(bfsInfo[1], {distance: 3, predecessor: 4});
Program.assertEqual(bfsInfo[2], {distance: 1, predecessor: 3});
Program.assertEqual(bfsInfo[3], {distance: 0, predecessor: null});
Program.assertEqual(bfsInfo[4], {distance: 2, predecessor: 2});
Program.assertEqual(bfsInfo[5], {distance: 2, predecessor: 2});
Program.assertEqual(bfsInfo[6], {distance: 1, predecessor: 3});
Program.assertEqual(bfsInfo[7], {distance: null, predecessor: null});
*/

Analysis of breadth-first search

How long does breadth-first search take for a graph with vertex set $V$ and edge set $E$? The answer is $O(V+E)$ time.

Let's see what $O(V+E)$ time means. Assume for the moment that $∣E∣≥∣V∣$, which is the case for most graphs, especially those for which we run breadth-first search. Then $∣V∣+∣E∣≤∣E∣+∣E∣=2⋅∣E∣$. Because we ignore constant factors in asymptotic notation, we see that when $∣E∣≥∣V∣$, $O(V+E)$ really means $O(E)$. If, however, we have $∣E∣<∣V∣$, then $∣V∣+∣E∣≤∣V∣+∣V∣=2⋅∣V∣$, and so $O(V+E)$ really means $O(V)$. We can put both cases together by saying that $O(V+E)$ really means $O(max⁡(V,E))$. In general, if we have parameters $x$ and $y$, then $O(x+y)$ really means $O(max⁡(x,y))$.

(Note, by the way, that a graph is connected if there is a path from every vertex to all other vertices. The minimum number of edges that a graph can have and still be connected is $∣V∣−1$. A graph in which $∣E∣=∣V∣−1$ is called a free tree.)

How is it that breadth-first search runs in $O(V+E)$ time? It takes $O(V)$ time to initialize the distance and predecessor for each vertex ($Θ(V)$ time, actually). Each vertex is visited at most one time, because only the first time that it is reached is its distance null, and so each vertex is enqueued at most one time. Since we examine the edges incident on a vertex only when we visit from it, each edge is examined at most twice, once for each of the vertices it's incident on. Thus, breadth-first search spends $O(V+E)$ time visiting vertices.