Запропонувати правку

Покращити цю статтю

Допрацюйте відповідь до «Що робить черга в BFS на графах?». Ваші зміни проходять модерацію перед публікацією.

Потрібне підтвердження

Контент

Що ви змінюєте

Заголовок (UA)

Коротка відповідь (UA)

Показується над повною відповіддю для швидкого нагадування.

Відповідь (UA)

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

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

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

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

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

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

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

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

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

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

- Вершини видаляються в порядку незростання відстані від джерела.
- Кожна вершина потрапляє в чергу не більше одного разу (якщо позначати 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)

```js
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: дві черги від джерела і цілі для прискорення на неорієнтованих графах.

Markdown · перетягуйте зображення · ⌘B / ⌘I шорткати715 слів

Для рев’юера

Примітка для модератора (необов’язково)

Бачить лише модератор. Прискорює рев’ю.