Breadth-First Search

Graphmedium#9

Explore level by level using a queue — finds shortest path

Ready

Step 1 of 0

Speed

Algorithm Code

1function bfs(grid, start, end) {
2  const queue = [start];
3  const visited = new Set();
4  visited.add(key(start));
5  while (queue.length > 0) {
6    const [r, c] = queue.shift();
7    if (r === end[0] && c === end[1]) return true;
8    for (const [dr, dc] of dirs) {
9      const nr = r+dr, nc = c+dc;
10      if (valid(nr,nc) && !visited.has(key(nr,nc))) {
11        visited.add(key(nr, nc));
12        queue.push([nr, nc]);
13      }
14    }
15  }
16  return false;
17}

Best

O(V + E)

Average

O(V + E)

Worst

O(V + E)

Space

O(V)

About Breadth-First Search

BFS explores all nodes at the current depth level before moving to nodes at the next depth level. It uses a queue (FIFO) and guarantees finding the shortest path in unweighted graphs. Essential for level-order traversal, shortest path, and connected components.

Time Complexity: Best: O(V + E), Average: O(V + E), Worst: O(V + E). Space: O(V).

Breadth-First Search

Graphmedium#9

Explore level by level using a queue — finds shortest path

Ready

Step 1 of 0

Speed

Algorithm Code

1function bfs(grid, start, end) {
2  const queue = [start];
3  const visited = new Set();
4  visited.add(key(start));
5  while (queue.length > 0) {
6    const [r, c] = queue.shift();
7    if (r === end[0] && c === end[1]) return true;
8    for (const [dr, dc] of dirs) {
9      const nr = r+dr, nc = c+dc;
10      if (valid(nr,nc) && !visited.has(key(nr,nc))) {
11        visited.add(key(nr, nc));
12        queue.push([nr, nc]);
13      }
14    }
15  }
16  return false;
17}

Best

O(V + E)

Average

O(V + E)

Worst

O(V + E)

Space

O(V)

About Breadth-First Search

Time Complexity: Best: O(V + E), Average: O(V + E), Worst: O(V + E). Space: O(V).