Що таке Breadth-First Search (пошук у ширину)?

АлгоритмиJunior~3 хв читання

Коротка відповідь

Breadth-First Search (BFS, пошук у ширину) - це алгоритм обходу графа/дерева, який відвідує вершини «по шарах» від стартової вершини, використовуючи чергу. Він гарантує знаходження найкоротшого шляху за кількістю ребер у неважених графах і працює за O(V+E) за часом і O(V) за пам'яттю.

Розгорнута відповідь

Визначення

BFS - це алгоритм, який починає обхід із заданої стартової вершини і послідовно відвідує всі вершини на відстані 1 ребро, потім відстані 2 ребра і так далі. Для керування порядком відвідування використовується черга (FIFO). Такий «шаровий» обхід дозволяє коректно вимірювати мінімальну кількість ребер від джерела до кожної досяжної вершини в неваженому графі.

Ключова ідея

Помістити стартову вершину в чергу, позначити її як відвідану, встановити відстань до неї рівною 0.
Поки черга не порожня: витягти вершину u з початку черги, «розширити» її - пройти по всіх сусідах v.
Якщо сусід v ще не відвіданий: позначити відвідування при додаванні в чергу, записати батька v = u, відстань dist[v] = dist[u] + 1, покласти v у кінець черги.

Властивості і гарантії

Шаровість: вершини відвідуються в порядку незростання найкоротшої відстані від джерела.
Найкоротші шляхи в неважених графах: BFS знаходить мінімальну кількість ребер від джерела до кожної досяжної вершини.
Працює і для орієнтованих, і для неорієнтованих графів (з урахуванням напрямку ребер).
Підходить для дерев (дає обхід по рівнях, level-order traversal).

Складність

Час: O(V + E), де V - кількість вершин, E - кількість ребер.
Пам'ять: O(V) для черги, масивів dist/visited/parent.

Структури даних

Черга (FIFO) - керує порядком обходу рівнів.
visited - позначає, що вершину вже поставлено в чергу (важливо позначати при додаванні, а не при вилученні).
dist - відстань у ребрах від джерела до вершини.
parent - батько вершини в дереві BFS для відновлення шляху.

Псевдокод (JavaScript)

function bfs(adj, start) {
  const n = adj.length;
  const dist = Array(n).fill(Infinity);
  const parent = Array(n).fill(-1);
  const visited = Array(n).fill(false);
  const q = [];
  let head = 0; // реалізація черги через масив і покажчик голови

  q.push(start);
  visited[start] = true;
  dist[start] = 0;

  while (head < q.length) {
    const u = q[head++];
    for (const v of adj[u]) {
      if (!visited[v]) {
        visited[v] = true;        // позначаємо при додаванні
        parent[v] = u;            // запам'ятовуємо дерево BFS
        dist[v] = dist[u] + 1;    // відстань по шарах
        q.push(v);
      }
    }
  }
  return { dist, parent, visited };
}

Відновлення шляху (по parent)

Після BFS можна відновити найкоротший шлях від s до t, підіймаючись по parent від t до s і розвертаючи послідовність.

function getPath(parent, s, t) {
  const path = [];
  for (let v = t; v !== -1; v = parent[v]) path.push(v);
  path.reverse();
  return path[0] === s ? path : []; // якщо t недосяжний, повернемо порожній шлях
}

Приклад: найкоротший шлях у неорієнтованому графі

Граф заданий списками суміжності. Знайдемо найкоротший шлях від 0 до 5.

const adj = [
  /*0*/ [1, 2],
  /*1*/ [0, 3, 4],
  /*2*/ [0, 4],
  /*3*/ [1, 5],
  /*4*/ [1, 2, 5],
  /*5*/ [3, 4]
];

const { dist, parent } = bfs(adj, 0);
console.log('dist to 5:', dist[5]);          // 3
console.log('path 0->5:', getPath(parent, 0, 5)); // наприклад [0,1,3,5] або [0,2,4,5]

Приклад: обхід дерева по рівнях (Level-Order Traversal)

Для дерев BFS відповідає обходу по рівнях: спочатку корінь, потім усі вузли глибини 1, потім глибини 2 і так далі.

class Node {
  constructor(val, left = null, right = null) {
    this.val = val; this.left = left; this.right = right;
  }
}

function levelOrder(root) {
  if (!root) return [];
  const res = [];
  const q = [root];
  let head = 0;
  while (head < q.length) {
    const levelSize = q.length - head;
    const level = [];
    for (let i = 0; i < levelSize; i++) {
      const node = q[head++];
      level.push(node.val);
      if (node.left) q.push(node.left);
      if (node.right) q.push(node.right);
    }
    res.push(level);
  }
  return res;
}

// Приклад дерева:      1
//                    / \
//                   2   3
//                  / \   \
//                 4   5   6
const root = new Node(1, new Node(2, new Node(4), new Node(5)), new Node(3, null, new Node(6)));
console.log(levelOrder(root)); // [[1],[2,3],[4,5,6]]

BFS на сітці (grid): найкоротший шлях із перешкодами

Клітини зі значенням 0 - прохідні, 1 - перешкоди. Ходимо в 4 напрямках. BFS видасть довжину найкоротшого шляху в кроках.

function shortestPathGrid(grid, start, goal) {
  const m = grid.length, n = grid[0].length;
  const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
  const dist = Array.from({ length: m }, () => Array(n).fill(Infinity));
  const q = [];
  let head = 0;
  const [sx, sy] = start, [gx, gy] = goal;
  if (grid[sx][sy] === 1 || grid[gx][gy] === 1) return -1;

  dist[sx][sy] = 0;
  q.push([sx, sy]);

  while (head < q.length) {
    const [x, y] = q[head++];
    if (x === gx && y === gy) return dist[x][y];
    for (const [dx, dy] of dirs) {
      const nx = x + dx, ny = y + dy;
      if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] === 0 && dist[nx][ny] === Infinity) {
        dist[nx][ny] = dist[x][y] + 1;
        q.push([nx, ny]);
      }
    }
  }
  return -1; // шляху до цілі немає
}

const grid = [
  [0,0,1,0],
  [0,0,0,0],
  [1,0,1,0],
  [0,0,0,0]
];
console.log(shortestPathGrid(grid, [0,0], [3,3]));

Варіації і застосування

Найкоротші шляхи в неважених графах і сітках (у кроках/ребрах).
Визначення досяжності і відстаней від джерела до всіх вершин.
Перевірка зв'язності/підрахунок компонент зв'язності (запускаючи BFS із невідвіданих вершин).
Перевірка двочастковості графа: розфарбування по рівнях (чергування кольорів).
Мультиджерельний BFS: стартуємо з множини вершин одразу (відстань 0), корисно для задач «хвильового» поширення.

BFS vs DFS

BFS використовує чергу і йде по шарах; DFS використовує стек/рекурсію і йде в глибину.
BFS знаходить найкоротший шлях у неважених графах; DFS такої гарантії не дає.
Пам'ять: BFS може споживати більше пам'яті на широких рівнях; DFS зазвичай економніший за пам'яттю.

Коли BFS не підходить

Важені графи з різними вагами: потрібен Дейкстра (або 0-1 BFS для ваг 0/1, або A* з евристикою).
Дуже широкі графи/рівні - високе споживання пам'яті.

Часті помилки

Позначати visited занадто пізно (при вилученні з черги), через що вузли можуть потрапити в чергу кілька разів.
Використовувати стек замість черги - отримаєте DFS, а не BFS.
Забувати ініціалізувати dist/parent/visited для кожного запуску BFS.
Неправильно враховувати напрямок ребер в орієнтованих графах.

Коротка відповідь

Для співбесіди

Premium

Коротка відповідь допоможе вам впевнено відповідати на цю тему під час співбесіди.