Към съдържанието
wannacode

BFS: най-малко спирки

Накратко: BFS (търсене в ширина) обхожда графа на слоеве с опашка и намира пътя с най-малко ребра за O(V + E).

Проблем

Шест улици вместо четири

Диспечерът на куриерите иска маршрут от склада до болницата с най-малко улици. В града всяка улица е светофар, завой и спиране, затова броят улици е по-важен от метрите.

Колегата е написал търсене, което тръгва по първата свободна улица и продължава, докато стигне. Ако заседне, се връща и опитва следващата:

function anyRoute(graph, at, target, seen) {
  if (at === target) return [at];
  seen.add(at);
  for (const next of graph.get(at)) {
    if (seen.has(next)) continue;
    const rest = anyRoute(graph, next, target, seen);
    if (rest !== null) return [at, ...rest];
  }
  return null;
}
const route = anyRoute(graph, "Склад", "Болница", new Set());
console.log(`${route.join(" → ")}: ${route.length - 1} улици`);
Изход
Склад → Гара → Площад → Пазар → Парк → Стадион → Болница: 6 улици

Път има, но е с 6 улици. Погледни картата от предишния урок: Склад → Гара → Площад → Кино → Болница са 4. Търсенето не е сгрешило: то не е питало за най-краткия, а е взело първия, който е намерило.

Идеята

Вълна от склада

Представи си, че от склада тръгва вълна. Първо стига до всички спирки на една улица разстояние. После от тях до всички нови на две. После на три. Спирка, до която вълната е стигнала, вече е заета: следващите вълни не я пипат.

Така спирката получава разстояние в момента, в който вълната я докосне за първи път, а то е най-малкото възможно.

Редът „първо по-близките“ го пази опашка: откритите спирки влизат отзад, а обработваната излиза отпред. Това е BFS (breadth-first search, обхождане в ширина).

  • dist пази разстоянието на всяка открита спирка. Той е и множеството на видените: спирка с dist не влиза в опашката втори път.
  • prev пази откъде е открита всяка спирка. С него после се връща самият път.

Виж го

Слой по слой

function bfs(graph, start) {
  const dist = new Map([[start, 0]]);
  const prev = new Map();
  const queue = [start];
  for (let head = 0; head < queue.length; head++) {
    const stop = queue[head];
    for (const next of graph.get(stop)) {
      if (dist.has(next)) continue;
      dist.set(next, dist.get(stop) + 1);
      prev.set(next, stop);
      queue.push(next);
    }
  }
  return { dist, prev };
}

function bfs(graph, start) {
  const dist = new Map([[start, 0]]);
  const prev = new Map();
  const queue = [start];
  for (let head = 0; head < queue.length; head++) {
    const stop = queue[head];
    for (const next of graph.get(stop)) {
      if (dist.has(next)) continue;
      dist.set(next, dist.get(stop) + 1);
      prev.set(next, stop);
      queue.push(next);
    }
  }
  return { dist, prev };
}


function pathTo(prev, target) {
  const path = [];
  let at = target;
  while (at !== undefined) {
    path.push(at);
    at = prev.get(at);
  }
  return path.reverse();
}
Стъпка по стъпка, с думи
  1. Започваме от Склад: dist = 0 и е единствената спирка в опашката.
  2. Склад излиза от опашката. Съседите Гара и Пазар са нови: dist = 1, prev = Склад, и влизат в края на опашката.
  3. Гара: Склад вече има dist и се прескача. Площад получава dist = 2.
  4. Пазар също вижда Площад, но Площад вече е в опашката с dist = 2. Всяка спирка влиза в опашката само веднъж. Парк: dist = 2.
  5. Слой 2 излиза от опашката и отваря слой 3: Кино отвъд моста и Стадион. В опашката има най-много два слоя, по-близкият е отпред.
  6. Кино открива Болница: dist = 4. Когато и Стадион стигне до нея, тя вече има dist: първото пристигане е най-краткото.
  7. Около Болница няма нищо ново. Опашката е празна: всяка спирка има разстоянието си от Склад.
  8. pathTo върви назад по prev: Болница ← Кино ← Площад ← Гара ← Склад. Обърнат, това е маршрутът: 4 улици.

Програмата пуска BFS от склада, печата разстоянието до всяка спирка и пътя до болницата:

const { dist, prev } = bfs(graph, "Склад");
for (const stop of stops) {
  console.log(`${stop}: ${dist.get(stop)}`);
}
const path = pathTo(prev, "Болница");
console.log(`${path.join(" → ")}: ${path.length - 1} улици`);
Изход
Склад: 0
Гара: 1
Пазар: 1
Площад: 2
Парк: 2
Кино: 3
Болница: 4
Стадион: 3
Склад → Гара → Площад → Кино → Болница: 4 улици

Масивът е опашка с индекс head: push слага отзад, а head показва коя е отпред. Нищо не се маха от началото на масива (защо, виж „По-точно“ по-долу). Как работи опашката отвътре, е в урока „Стек и опашка“.

Пробвай

Подреди редовете

Това е сърцето на BFS: едно завъртане на цикъла. Подреди редовете:

  1. const stop = queue[head];
  2. }
  3. if (dist.has(next)) continue;
  4. prev.set(next, stop);
  5. dist.set(next, dist.get(stop) + 1);
  6. for (const next of graph.get(stop)) {
  7. queue.push(next);

Пробвай

Предвиди изхода

Същият BFS, но тръгва от Кино. Какво печата програмата за Склад, Стадион и Парк?

const { dist } = bfs(graph, "Кино");
const ask = ["Склад", "Стадион", "Парк"];
console.log(ask.map((s) => dist.get(s)).join(" "));
Отговор

Идеята

Пътят назад

dist казва колко улици са, но не кои. Пътят е в prev: Болница е открита от Кино, Кино от Площад, Площад от Гара, Гара от Склад. Склад няма prev, защото оттам е тръгнало всичко.

Затова пътят се чете отзад напред: от целта по prev до началото, а накрая се обръща.

function pathTo(prev, target) {
  const path = [];
  let at = target;
  while (at !== undefined) {
    path.push(at);
    at = prev.get(at);
  }
  return path.reverse();
}
let at = target;
while (at !== undefined) {
  path.push(at);
  at = ;
}
По-точно, за любопитните

Пътищата в prev образуват дърво: всяка спирка сочи една-единствена, тази, от която е открита, а коренът е складът. Това се казва дърво на BFS. Всеки клон от корена до спирка е най-краткият път до нея. Затова един BFS от склада дава най-късите пътища до всички спирки наведнъж, не само до болницата.

Ако спирката изобщо не е открита (няма път), тя няма dist. Провери това, преди да викаш pathTo: иначе ще получиш „път“ от една спирка, самата цел.

Идеята

Защо първото пристигане е най-краткото

Опашката държи най-много два слоя: d и d + 1, като по-близкият е отпред. Спирка на d + 1 улици се открива от спирка на d улици, а спирките на d + 2 идват чак когато започнат да излизат тези на d + 1. Затова спирката получава dist от най-краткия път, а всеки по-късен път до нея е поне толкова дълъг и се прескача.

Тук е важно и кога спирката се отбелязва като видяна: в момента, в който влиза в опашката, а не когато излиза. Иначе Площад, който се вижда и от Гара, и от Пазар, щеше да влезе два пъти.

По-точно, за любопитните

Доказателството в една фраза: по индукция по d, всички спирки на разстояние d излизат от опашката преди всички на разстояние d + 1, и всяка получава dist = d. Това важи само ако всяко ребро струва 1. Ако улиците имат различни дължини, по-малко улици не значи по-малко метри. Тогава опашката се сменя с приоритетна опашка по изминатото разстояние, и това е Dijkstra (урокът за Dijkstra в този модул).

Идеята

Колко струва

Всяка спирка влиза в опашката най-много веднъж и излиза веднъж. Когато излезе, поглежда своите улици. Двупосочна улица се вижда от двата си края. Общо: V излизания и 2E погледа, O(V + E).

Това важи за списък от съседи. С матрица „кои са съседите“ е целият ред, и BFS прави V погледа на спирка: O(V²). Пусни и двата върху град-решетка от n кръстовища:

  • BFS със списък от съседи O(n)
  • BFS с матрица O(n²)
Алгоритъмn = 10n = 1000n = 5000n = 100 000
BFS със списък от съседи36487224 716498 734
BFS с матрица1101 001 00025 005 000≈ 10 002 000 000
Кодът се пуска в твоя браузър на JavaScript. Броят операции е същият на всеки език, защото алгоритъмът е същият. Времето зависи от машината, затова е само за сравнение. „≈“ е оценка по кривата: толкова голямо n не пускаме, за да не замръзне страницата.
function bfs(graph, start) {
  const dist = new Map([[start, 0]]);
  const prev = new Map();
  const queue = [start];
  for (let head = 0; head < queue.length; head++) {
    const stop = queue[head];
    for (const next of graph.get(stop)) {
      if (dist.has(next)) continue;
      dist.set(next, dist.get(stop) + 1);
      prev.set(next, stop);
      queue.push(next);
    }
  }
  return { dist, prev };
}

Броят се всяка спирка, излязла от опашката, и всеки поглед към съсед. При 1000 кръстовища списъкът прави 4 872 операции, а матрицата 1 001 000. При 100 000 кръстовища списъкът прави 498 734, около 5 на кръстовище: едно излизане и до 4 улици. Матрицата при 5000 вече е 25 005 000.

Пробвай

Намери грешката

Колега реши, че разстоянието на новата спирка е „следващият номер“. Програмата печата:

function bfs(graph, start) {
  const dist = new Map([[start, 0]]);
  const prev = new Map();
  const queue = [start];
  for (let head = 0; head < queue.length; head++) {
    const stop = queue[head];
    for (const next of graph.get(stop)) {
      if (dist.has(next)) continue;
      dist.set(next, dist.size);
      prev.set(next, stop);
      queue.push(next);
    }
  }
  return { dist, prev };
}
Изход
Склад: 0
Гара: 1
Пазар: 2
Площад: 3
Парк: 4
Кино: 5
Болница: 7
Стадион: 6
Склад → Гара → Площад → Кино → Болница: 4 улици

Пътят е верен, 4 улици, а Болница излиза на 7. На кой ред е грешката?

Избери реда с грешката.

По-точно

Опашката във всеки език

JavaScript няма вградена опашка. queue.shift() маха първия елемент и по спецификация мести всички останали: O(n) на взимане. Масивът с индекс head не маха нищо, само мести индекса: O(1). Цената е, че масивът пази всички минали спирки до края на BFS, но те са V на брой, колкото и dist.

Упражнение

Слоевете на града

Реши задачата в редактора си.

Слоеве и мостове. С BFS от склада изведи спирките по слоеве (спирките на всеки слой в реда на stops) и най-далечната спирка. После затвори двата моста: махни ги от списъка от съседи, пусни BFS пак и изведи до кои спирки вече не се стига.

const bridges = [
  ["Пазар", "Парк"], ["Площад", "Кино"],
];
Изход
Слой 0: Склад
Слой 1: Гара, Пазар
Слой 2: Площад, Парк
Слой 3: Кино, Стадион
Слой 4: Болница
Най-далеч: Болница (4 улици)
Без мостовете не се стига до: Парк, Кино, Болница, Стадион

Още задачи

  • Най-близката аптека. Някои спирки имат аптека. Пусни един BFS, който тръгва едновременно от всички аптеки (всички са в опашката с dist 0), и изведи за всяка спирка колко улици я делят от най-близката.
  • Лабиринт от сгради. Складът е решетка от рафтове (#) и пътеки (.). Намери най-малко стъпки от входа до изхода, като съседите на клетка са горе, долу, ляво и дясно.
  • Всички най-къси. Преброй колко различни най-къси пътя има от склада до всяка спирка.

Тест

Провери се

1. Защо първият път, по който BFS стига до спирка, е най-краткият в улици?
2. Колега смени опашката със стек: взима последната добавена спирка. Какво става?
3. Улиците имат дължини в метри. Дава ли BFS най-краткия път в метри?
4. Колко работа прави BFS върху град с V кръстовища и E улици, пазен като списък от съседи?

Създаден от Иво Гергов като част от кампанията на Evo Tech за достъпно обучение по програмиране ·