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

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

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

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

Контент

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

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

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

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

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

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

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

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

### Ідея алгоритму

BFS обходить граф шарами (рівнями) відносно стартової вершини. Для керування порядком відвідування використовується черга: спочатку обробляються вершини поточного рівня, потім - наступного.

1. Ініціалізуємо відстані як нескінченність, батьків як null.
2. Кладемо стартову вершину в чергу, відстань до неї = 0.
3. Поки черга не порожня: видаляємо вершину u і для кожного її сусіда w, який ще не відвіданий, записуємо dist[w] = dist[u] + 1, parent[w] = u і додаємо w у чергу.

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

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

### Складність

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

### Псевдокод

```text
BFS(G, s):
  for v in V(G):
    dist[v] = INF
    parent[v] = null
  dist[s] = 0
  Q = queue()
  Q.enqueue(s)

while not Q.empty():
    u = Q.dequeue()
    for w in adj[u]:
      if dist[w] == INF:        # w ще не відвіданий
        dist[w] = dist[u] + 1
        parent[w] = u
        Q.enqueue(w)

# Після виконання:
# dist[v] - довжина найкоротшого шляху по ребрах від s до v (або INF, якщо недосяжна)
# parent[v] - попередник v у дереві BFS (для відновлення шляху)
```

### Реалізація на JavaScript/TypeScript

```typescript
type Graph = Record<string, string[]>;

function bfs(graph: Graph, start: string) {
  const dist: Record<string, number> = {};
  const parent: Record<string, string | null> = {};

for (const v in graph) {
    dist[v] = Infinity;
    parent[v] = null;
  }

const queue: string[] = [];
  let head = 0; // покажчик на голову черги для O(1) dequeue

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

while (head < queue.length) {
    const u = queue[head++];
    for (const w of graph[u]) {
      if (dist[w] === Infinity) { // не відвіданий
        dist[w] = dist[u] + 1;
        parent[w] = u;
        queue.push(w);
      }
    }
  }

return { dist, parent };
}

function reconstructPath(parent: Record<string, string | null>, target: string) {
  const path: string[] = [];
  let cur: string | null = target;
  while (cur !== null) {
    path.push(cur);
    cur = parent[cur];
  }
  path.reverse();
  return path;
}

// Приклад використання
const graph: Graph = {
  A: ["B", "C"],
  B: ["A", "D", "E"],
  C: ["A", "F"],
  D: ["B"],
  E: ["B", "F"],
  F: ["C", "E"],
};

const { dist, parent } = bfs(graph, "A");
console.log(dist["F"]); // 2 - найкоротша кількість ребер A->F
console.log(reconstructPath(parent, "F")); // Наприклад: [ 'A', 'C', 'F' ] (один з найкоротших шляхів)
```

### Приклад роботи на графі

Нехай старт - вершина A. Рівні (відстані) будуть такими:

- Рівень 0: A
- Рівень 1: B, C (сусіди A)
- Рівень 2: D, E, F (сусіди B і C, ще не відвідані)

Звідси відстань до F дорівнює 2 (наприклад, шлях A → C → F). Якщо існує кілька найкоротших шляхів, BFS поверне той, що виник першим, виходячи з порядку сусідів у списку суміжності.

### Застосування

- Пошук найкоротшого шляху в незважених графах і на решітках (лабіринти).
- Перевірка зв'язності, пошук компонент зв'язності (запускаючи BFS з кожної невідвіданої вершини).
- Перевірка двочастковості графа (розфарбування за рівнями у два кольори).
- Обчислення рівнів/шарів у графі, побудова дерева BFS.
- Топологічне сортування алгоритмом Кана (варіант BFS за вхідними степенями для DAG).

### Варіації

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

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

- Позначати вершину відвіданою лише під час видалення з черги - це може призвести до багаторазового додавання того самого вузла. Правильно позначати під час постановки в чергу.
- Застосовувати BFS до графів із довільними додатними вагами як до незважених - шляхи не будуть оптимальними (потрібен Дейкстра).
- Забувати враховувати напрямленість ребер в орієнтованому графі.
- Неправильна ініціалізація відстаней (наприклад, 0 замість нескінченності для невідвіданих).

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

- Граф з довільними невід'ємними вагами - використовуйте Дейкстру (або 0-1 BFS для ваг 0/1).
- Від'ємні ваги - алгоритми Беллмана-Форда/SPFA.
- Дуже щільні або величезні графи можуть упиратися в пам'ять/час через зберігання черги і списків суміжності.

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

Для рев’юера

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

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