Що робить алгоритм BFS на графах (Breadth-First Search)?

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

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

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

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

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

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

Ініціалізуємо відстані як нескінченність, батьків як null.
Кладемо стартову вершину в чергу, відстань до неї = 0.
Поки черга не порожня: видаляємо вершину 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.
Дуже щільні або величезні графи можуть упиратися в пам'ять/час через зберігання черги і списків суміжності.

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

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

Premium

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