GitHub Repository Submission

When using GitHub mode, paste your repository URL below and click Save URL to store it. The saved URL will be automatically included with every message you send until you choose to clear it. Learn more

Your GitHub repository URL is saved. LSBot will automatically fetch your latest code from this repository for each message. To change the URL, clear it first and save a new one.

Exercise 2

Breadth-First Search (BFS)

In graphs, Breadth-First Search (BFS) is commonly used to explore vertices level by level, meaning that all vertices at the present depth are processed before moving on to the vertices at the next depth level.

We can perform BFS using a queue, which ensures that we process vertices in the order they are discovered.

Try implementing the solution on your own first. If you need help, refer to the walkthrough or the solution code.

// Implement a function `bfs` that accepts two arguments: the adjacency list
// representing an acyclic graph and a starting vertex (source).
// The function should print the vertices in breadth-first
// traversal order.

function bfs(adjList, source) {
  // implementation goes here
}

const adjList = new Map();
adjList.set(1, []);
adjList.set(2, [1, 3, 4]);
adjList.set(3, [5]);
adjList.set(4, [6]);
adjList.set(5, []);
adjList.set(6, []);
adjList.set(7, [6]);

bfs(adjList, 2); // 2, 1, 3, 4, 5, 6  or 2, 4, 3, 1, 6, 5

// Again, the order depends on which neighbor node we explore first

Solution

We want to process the vertices in breadth-first traversal order. This means processing the current vertex (node)—in this case, printing its value—and then exploring its neighbors level by level.

To implement BFS using a queue:

  • Start with the queue containing the first (source) vertex.
  • Iterate until there are no elements left in the queue:
    • In each iteration, dequeue the element from the front of the queue and process it (print it).
    • Iterate through the neighbors of the dequeued vertex and enqueue those neighbor vertices.

Let's do a visual walkthrough using this graph:

Step 1: We begin with the source vertex already in the queue.

Step 2: In the first iteration, we dequeue the vertex from the queue, process it by printing it, and then add its neighbors to the queue. Again, the order in which we enqueue its neighbors will be the order in which they appear in the adjacency list. First vertex 1, then vertex 3, and finally vertex 4.

Step 3: In the next iteration, we dequeue the first element in the queue, vertex 1, and process it by printing it. This vertex has no outgoing neighbors, so we can move to our next iteration.

Step 4: Now, we dequeue vertex 3 from the queue and process it. Next, we add its neighbor, vertex 5, to the queue.

Step 5: In the fourth iteration, we dequeue vertex 4 from the queue and process it. Its sole outgoing neighbor is vertex 6, so we enqueue 6.

Step 6: We dequeue vertex 5 from the queue and process it. There aren't any outgoing neighbors, so we continue.

Step 7: Finally, we dequeue vertex 6 from the queue. We process it by printing it. Since it doesn't have outgoing neighbors and the queue is empty, we are finished with the traversal.

Solution Code

function bfs(adjList, source) {
  let queue = [source];

  while (queue.length !== 0) {
    let current = queue.shift();
    console.log(current);

    let neighbors = adjList.get(current);
    for (let neighbor of neighbors) {
      queue.push(neighbor);
    }
  }
}

Hi! I'm LSBot. I can help you think through the selected exercise by giving you hints and guidance without revealing the solution. Your code from the editor will be automatically detected. Want to know more? Refer to the LSBot User Guide .

Detected solution
Loading...

Submit your solution for LSBot review.

 Hi! I'm LSBot. Your code from the editor will be automatically detected. I'll review your solution and provide feedback to help you improve. Ask questions about your solution or request a comprehensive code review. Want to know more? Refer to the LSBot User Guide .

Detected solution
Loading...