Print BFS implementation in JavaScript

Question

Given a graph and a starting vertex print the value of each vertex in a breadth first order.

Let's code out a general BFS algorithm printing each vertex's value in a BFS order. We are given a graph in the form of an adjacency list, as well as a starting vertex.

To analyze the complexity of a graph, we need to consider the number of vertices (V) and the number of Edges (E) as independent variables. Also, we need to consider the type of edge representation for the graph. We will go over the analysis for adjacency list.

Pseudocode
1. Create a queue to hold neighbor vertices and add the start vertex.
2. Create a set to track visited vertices and add the start vertex.
3. While queue is not empty
 4. Dequeue from the queue and set to current.
 5. Loop through all the vertex's neighbors.
 6. For each neighbor, check if the vertex has been visited.
 7. If not visited, then add it to the queue and add mark it as visited.
 8. Operate on current
9. Once the queue is empty, we have completed the BFS

Here's the code in JavaScript:

function graphBFS(graph, start) {
 let queue = new Queue(); // 1
 let visited = new Set(); // 1
 let current; // 1
 let neighbors; // 1
 queue.enqueue(start); // 1
 visited.add(start); // 1
 // while loop will run a total of V times
 while (queue.length > 0) { // 1 (for break condition)
 current = queue.dequeue(); // 1
 neighbors = graph.neighbors(current); // 1 (for adjacency list)
 // the for loop will run based on d (degree) on average is E/V
 for (let i = 0; i < neighbors.length; i++) { // 1
 if (!visited.has(neighbors[i]) { // 1
 queue.enqueue(neighbors[i]); // 1
 visited.add(neighbors[i]); // 1
 }
 // <-- operating on the current vertex will add additional time
 }
 }
}

Answer 1

Code review

Fail

You should ensure your code is at least able to be parsed before you ask for review. I will assume it an oversight (that even your code formater was glaringly pointing out) and review assuming the missing token.

Incomplete

As an exercise the real complexity is in the graph and the neighbors function for which there is no code to evaluate.

The Queue implementation is missing, JS Arrays are queues, using push and shift to move items through the (abstracted) "queue".

Poor style

The code can be written better.

• Use const for variables that don`t change
• Its a little noisy. Remove redundant code eg while(foo.length > 0) the length property will never be < 0 so while(foo.length) does the same with less
• Use appropriate iterators, for(;;) loops only when you need the index, else use the for(of) loop
• There is really no need for the variables current and neighbors however neighbors can be argued to help with readability (see rewrite)
• The comments are of no useful value.
  • Never add comments without relevance to the code. Why the many // 1?
  • Don't state the obvious. // 1 (for break condition)
  • Comment must be consistent with the naming and abstractions used. // 1 (for adjacency list) don't you mean neighbours?
• Bad indentation is the worst possible readability error you can introduce into your source code. If assessing code, unindented blocks are an automatic fail and there is no argument that can ever justify such poor style.
• There is a syntax error, the code will not even make it past the parser. A basic requirement for code review. I am not going to point it out as your runtime environment will tell you.

Rewrite

Two acceptable options of the many possible.

function graphBFS(graph, start) {
 const queue = new Queue();
 const visited = new Set([start]);
 queue.enqueue(start);
 while (queue.length) {
 const neighbors = graph.neighbors(queue.dequeue());
 for (const neighbor of neighbors) {
 if (!visited.has(neighbor)) {
 queue.enqueue(neighbor);
 visited.add(neighbor);
 }
 }
 }
}

Or as

function graphBFS(graph, start) {
 const queue = [start], visited = new Set(queue);
 while (queue.length) {
 for (const item of graph.neighbors(queue.shift())) {
 if (!visited.has(item)) {
 queue.push(item);
 visited.add(item);
 }
 }
 }
} 

The latter I would score higher as it demonstrates a higher level of understanding of the problem being solved, reduced dependency and thus more portable and reusable, and reduced use of abstraction in favor of consistency.

EG If the function were to be change to depth first you need only change the function graph.neighbors and not rename neighbor 4 times due to strong coupling with the abstract. An item of neighbors is still meaningful as an item of roots (Or whatever you call the forward edge traverse)