Що робить черга в BFS на графах?

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

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

Черга в BFS зберігає «фронтир» - вершини, виявлені, але ще не оброблені, і видає їх у порядку FIFO. Це гарантує обхід пошарово (за зростанням кількості ребер від старту) і, як наслідок, знаходження найкоротших шляхів у незважених графах.

Детальна відповідь

Що робить черга в BFS?

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

Навіщо потрібна черга (основні ролі)

Зберігає фронтир: множину вершин, які вже знайдені, але ще не розширені.
Гарантує пошаровий порядок: вершини видаляються в порядку незростання відстані від джерела.
Забезпечує коректність найкоротших шляхів у незважених графах: перше відвідування вершини дає мінімальну кількість ребер до неї.
Допомагає уникнути повторної обробки: у парі з visited не допускає повторного додавання в чергу.

Як працює BFS крок за кроком

Ініціалізуємо visited, dist, parent. Кладемо стартову вершину s у чергу, позначаємо visited[s] = true, dist[s] = 0.
Поки черга не порожня: видаляємо вершину u з голови черги.
Для кожного сусіда v вершини u: якщо v ще не відвіданий, позначаємо visited[v] = true, dist[v] = dist[u] + 1, parent[v] = u і додаємо v у хвіст черги.
Повторюємо, поки не обробимо всі досяжні вершини.

Ключові інваріанти черги

Вершини видаляються в порядку незростання відстані від джерела.
Кожна вершина потрапляє в чергу не більше одного разу (якщо позначати visited при додаванні).
На момент видалення u всі вершини попереднього шару вже видалені й повністю розширені.

Чому саме черга, а не стек чи пріоритетна черга?

Стек (LIFO) призводить до DFS: заглиблення по одному шляху, найкоротші шляхи не гарантуються.
Пріоритетна черга змінює алгоритм (Дейкстра), потрібна для зважених графів з невід'ємними вагами. Це вже не класичний BFS.
Deque з pushFront перетворює обхід на варіації, що порушують пошаровість, якщо використовувати його неправильно.

Складність

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

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

Позначати visited при видаленні, а не при додаванні - призводить до дублювання в черзі.
Використовувати Array.shift() у JS - це O(n); краще зберігати індекс голови.
Не скидати структури між запусками BFS.
Застосовувати BFS до зваженого графа як до незваженого, очікуючи коректних найкоротших шляхів - це неправильно.

Приклад коду (JavaScript)

function bfs(adj, start) {
  const n = adj.length;
  const visited = Array(n).fill(false);
  const dist = Array(n).fill(Infinity);
  const parent = Array(n).fill(-1);

  // Черга з покажчиком голови (O(1) на операції)
  const queue = [];
  let head = 0;

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

  const order = []; // порядок видалення з черги

  while (head < queue.length) {
    const u = queue[head++]; // dequeue
    order.push(u);

    for (const v of adj[u]) {
      if (!visited[v]) {
        visited[v] = true;           // Важливо: позначаємо при додаванні
        dist[v] = dist[u] + 1;
        parent[v] = u;
        queue.push(v);               // enqueue
      }
    }
  }

  return { visited, dist, parent, order };
}

// Приклад графа (неорієнтований), вершини: 0..4
// 0-1, 0-2, 1-3, 2-3, 3-4
const adj = [
  [1, 2],   // 0
  [0, 3],   // 1
  [0, 3],   // 2
  [1, 2, 4],// 3
  [3]       // 4
];

const { dist, parent, order } = bfs(adj, 0);
console.log('Порядок видалення:', order);       // [0, 1, 2, 3, 4]
console.log('Відстані від 0     :', dist);       // [0, 1, 1, 2, 3]

// Відновлення шляху 0 -> 4
function restorePath(parent, t) {
  const path = [];
  for (let v = t; v !== -1; v = parent[v]) path.push(v);
  return path.reverse();
}
console.log('Найкоротший шлях 0→4:', restorePath(parent, 4)); // [0,1,3,4] або [0,2,3,4]

Міні-приклад: рівні обходу

Для графа з прикладу, починаючи з 0, черга забезпечує такі рівні:

Рівень 0: 0
Рівень 1: 1, 2
Рівень 2: 3
Рівень 3: 4

Корисні варіації

Мульти-джерело: покладіть у чергу одразу всі стартові вершини з dist = 0, щоб знайти відстані до найближчого джерела.
Раннє завершення: можна зупинитися, щойно видалили цільову вершину з черги - її dist уже мінімальний.
Двосторонній BFS: дві черги від джерела і цілі для прискорення на неорієнтованих графах.

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

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

Premium

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