JavaScript based Breadth-First Search

breadth-first-search.js

/* A Queue object for queue-like functionality over JavaScript arrays. */
var Queue = function() {
	this.items = [];
};
Queue.prototype.enqueue = function(obj) {
	console.log("enqueue: ", 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:
	while (!queue.isEmpty()) {
		//  Repeatedly dequeue a vertex u from the queue.
		var vertex = queue.dequeue();

		//  For each neighbor v of u that has not been visited:
		for (var i = 0; i < graph[vertex].length; i += 1) {
			var neighbor = graph[vertex][i];

			if (bfsInfo[neighbor].distance === null) {
				bfsInfo[neighbor].distance = bfsInfo[vertex].distance + 1;
				bfsInfo[neighbor].predecessor = vertex;

				queue.enqueue(neighbor);
			}
		}
	}

	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++) {
	console.log("vertex " + i + ": distance = " + bfsInfo[i].distance + ", predecessor = " + bfsInfo[i].predecessor);
}

console.log(bfsInfo[0].distance === 4, bfsInfo[0].predecessor === 1);
console.log(bfsInfo[1].distance === 3, bfsInfo[1].predecessor === 4);
console.log(bfsInfo[2].distance === 1, bfsInfo[2].predecessor === 3);
console.log(bfsInfo[3].distance === 0, bfsInfo[3].predecessor === null);
console.log(bfsInfo[4].distance === 2, bfsInfo[4].predecessor === 2);
console.log(bfsInfo[5].distance === 2, bfsInfo[5].predecessor === 2);
console.log(bfsInfo[6].distance === 1, bfsInfo[6].predecessor === 3);
console.log(bfsInfo[7].distance ===  null, bfsInfo[7].predecessor === null);