LietCode
Graph - Breadth-First Search (BFS)

Graph - Breadth-First Search (BFS)

Abhi's photo
Abhi
·

4 min read

Explain the Problem

Implement the Breadth-First Search (BFS) algorithm for graph traversal. Given a graph and a starting vertex, traverse the graph in breadth-first order and print the vertices in the order they are visited.

Example:

Input:

Graph: 
0: [1, 2]
1: [0, 3, 4]
2: [0, 4]
3: [1, 5]
4: [1, 2, 5]
5: [3, 4]

Starting Vertex: 0

Output:

0 1 2 3 4 5

Short, Easy-to-Remember Solution/Approach

To implement BFS for graph traversal, we can use a queue data structure:

  1. Initialize: Start by adding the starting vertex to the queue and mark it as visited.

  2. Process Queue: While the queue is not empty, remove a vertex from the queue, visit it, and add all its unvisited neighbors to the queue.

Solution in JavaScript with Code Commenting

Here's the JavaScript solution with detailed comments:

function bfs(graph, start) {
  const visited = new Set(); // Set to keep track of visited vertices
  const queue = [start]; // Queue for BFS

  while (queue.length > 0) {
    const vertex = queue.shift(); // Dequeue a vertex
    if (!visited.has(vertex)) {
      console.log(vertex); // Visit the vertex
      visited.add(vertex); // Mark the vertex as visited

      // Add all unvisited neighbors to the queue
      for (const neighbor of graph[vertex]) {
        if (!visited.has(neighbor)) {
          queue.push(neighbor);
        }
      }
    }
  }
}

// Example usage:
const graph = {
  0: [1, 2],
  1: [0, 3, 4],
  2: [0, 4],
  3: [1, 5],
  4: [1, 2, 5],
  5: [3, 4]
};

bfs(graph, 0);
// Output: 0 1 2 3 4 5

Imagine a Treasure Hunt in a Park

You're at the entrance of a big park, and there's a treasure hidden somewhere. You have a map that shows various landmarks like trees, benches, and fountains connected by paths. Your goal is to find the treasure in the shortest amount of time.

How BFS Works in the Treasure Hunt

  1. Start at the Entrance: You start at the entrance of the park. This is your starting point, and we'll call it Node A.

  2. Explore Nearby First: You look around and see which landmarks (nodes) are directly connected to Node A. Let's say Node A is connected to Node B (a tree) and Node C (a bench).

  3. Visit Each Landmark: You visit Node B (the tree) first, then come back to Node A, and then visit Node C (the bench). After visiting each landmark, you mark it as visited so you don't go there again.

  4. Use a Queue: You keep a list (queue) of places to visit next. You add Node B and Node C to the queue. A queue works like a line at a theme park ride: the first person in line gets to go first, and new people join the end of the line.

  5. Continue Exploring: After visiting Node B and Node C, you look at their neighboring nodes. Maybe Node B is connected to Node D (a fountain), and Node C is connected to Node E (a statue).

  6. Add Neighbors to the Queue: You add Node D and Node E to the end of the queue. Now your queue has Node D and Node E.

  7. Repeat the Process: You take the next item from the queue (Node D) and visit it. Then you take the next item (Node E) and visit it, and so on.

  8. Find the Treasure: You keep doing this until you visit all nodes. If you find the treasure at any node, you stop the search.

Key Points

  • Queue: Keeps track of nodes to visit next.

  • Visit Level by Level: You explore all nodes directly connected to your starting node first before moving further.

  • Mark Visited: You mark nodes as visited to avoid revisiting them.

Visualization

Queue: [A]
Visit: A
Queue: [B, C]
Visit: B
Queue: [C, D]
Visit: C
Queue: [D, E]
Visit: D
Queue: [E]
Visit: E
Queue: []

In this example, you started at A, explored nearby landmarks B and C, then explored further to D and E, all while keeping track of where to go next using a queue.

Why Use BFS?

BFS is great when you want to find the shortest path to something, like the treasure in the park, because it explores all possible paths level by level, ensuring you don't miss the shortest route. It's like making sure you check all nearby spots before going further away, so you find the treasure as quickly as possible.

Complexity Analysis

  • Time Complexity: O(V + E), where V is the number of vertices and E is the number of edges. This is because each vertex and edge is processed once.

  • Space Complexity: O(V), due to the storage of the queue and the visited set.

graph databaseBFS