DFS: търсене в дълбочина в JavaScript

Проблем

Градът, разрязан от реката

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

От урока за BFS знаеш как да намериш докъде се стига от склада. Но частите може да са много, и всяка трябва да се намери цялата. Трябва обход, който тръгва от всяка спирка, още без част, и маркира всичко, до което стига.

Има и втори проблем в същия град. Планът на доставките има правила „А се доставя преди Б“. Някой е добавил грешно правило, и вече няма ред, който да спазва всички. Кое правило е виновно?

Идеята

Докъдето стига улицата

DFS (depth-first search, обхождане в дълбочина) върви като човек в лабиринт: тръгва по първата улица към непозната спирка, оттам по първата към следващата непозната, и така, докато стигне спирка, около която всичко е видяно. Тогава се връща една спирка назад и опитва следващата ѝ улица.

С рекурсия връщането назад става само: visit за спирката вика visit за първия непознат съсед, и когато той свърши, цикълът продължава със следващия. Стекът на извикванията помни докъде е стигнала всяка спирка.

Всяка спирка получава номера на острова си веднага при влизане. Това е и множеството на видените: спирка с номер не се посещава втори път.
Остров (свързана компонента) е всичко, до което стига един visit. Цикълът по всички спирки пуска нов visit от всяка спирка без номер.

Виж го

Надолу и назад

function visit(graph, stop, island, islandOf) {
  islandOf.set(stop, island);
  for (const next of graph.get(stop)) {
    if (!islandOf.has(next)) {
      visit(graph, next, island, islandOf);
    }
  }
}

function islands(graph, stops) {
  const islandOf = new Map();
  let count = 0;
  for (const stop of stops) {
    if (islandOf.has(stop)) continue;
    count++;
    visit(graph, stop, count, islandOf);
  }
  return islandOf;
}

function visit(graph, stop, island, islandOf) {
  islandOf.set(stop, island);
  for (const next of graph.get(stop)) {
    if (!islandOf.has(next)) {
      visit(graph, next, island, islandOf);
    }
  }
}

function islands(graph, stops) {
  const islandOf = new Map();
  let count = 0;
  for (const stop of stops) {
    if (islandOf.has(stop)) continue;
    count++;
    visit(graph, stop, count, islandOf);
  }
  return islandOf;
}

Стъпка по стъпка, с думи

Двата моста са затворени. islands минава спирките по ред: Склад още няма остров, затова count = 1 и visit тръгва от него.
visit(Склад) му дава остров 1 и веднага слиза в първия съсед без остров: Гара. Склад чака сив в стека на извикванията.
Все по-надълбоко: Гара → Площад → Пазар. Четири извиквания са отворени едновременно и всяко чака по-горното.
Около Пазар всичко вече има остров. visit се връща и Пазар почернява. Назад по стека: и при Площад и Гара няма нищо ново.
Склад пак е отгоре. Последният му съсед Пазар вече е видян и първият обход свършва: остров 1 е Склад, Гара, Пазар, Площад. Затворените мостове са го спрели на реката.
Цикълът в islands продължава: Гара, Пазар и Площад вече имат остров и се прескачат. Парк няма: count = 2.
Същият обход на другия бряг: Парк → Стадион → Болница → Кино, после назад до Парк.
Два острова: по 4 спирки на всеки бряг. Всяка спирка получи номер веднъж, всяка улица беше погледната от двата края: O(V + E).

Програмата затваря мостовете, пуска islands и печата островите:

const closed = [
  ["Пазар", "Парк"], ["Площад", "Кино"],
];
for (const [a, b] of closed) {
  graph.set(a, graph.get(a).filter((s) => s !== b));
  graph.set(b, graph.get(b).filter((s) => s !== a));
}
const islandOf = islands(graph, stops);
const count = Math.max(...islandOf.values());
console.log(`Острови: ${count}`);
for (let i = 1; i <= count; i++) {
  const members = stops.filter((s) => islandOf.get(s) === i);
  console.log(`Остров ${i}: ${members.join(", ")}`);
}

Острови: 2
Остров 1: Склад, Гара, Пазар, Площад
Остров 2: Парк, Кино, Болница, Стадион

Номерът на острова пази Map, а броят им е най-големият номер в него.

Пробвай

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

Мостът Пазар – Парк е отворен, но около Кино се копае: затворени са Площад – Кино и Кино – Болница. Колко острова печата програмата?

const closed = [
  ["Площад", "Кино"], ["Кино", "Болница"],
];
for (const [a, b] of closed) {
  graph.set(a, graph.get(a).filter((s) => s !== b));
  graph.set(b, graph.get(b).filter((s) => s !== a));
}
const islandOf = islands(graph, stops);
const count = Math.max(...islandOf.values());
console.log(`Острови: ${count}`);

Отговор

Острови: 1

Острови: 2

Острови: 3

Идеята

Свой стек вместо рекурсия

Тук островите са по 4 спирки и рекурсията е дълбока 4 извиквания. В град-решетка от 100 000 кръстовища обходът в дълбочина може да слезе на десетки хиляди нива, а всяко ниво е рамка в стека на извикванията. Стекът е малък и се препълва. Как се превръща рекурсия в цикъл, е в урока „От рекурсия към цикъл“. Тук е същото: стекът става обикновена колекция.

function walk(graph, start) {
  const order = [];
  const seen = new Set();
  const stack = [start];
  while (stack.length > 0) {
    const stop = stack.pop();
    if (seen.has(stop)) continue;
    seen.add(stop);
    order.push(stop);
    const next = graph.get(stop);
    for (let i = next.length - 1; i >= 0; i--) {
      if (!seen.has(next[i])) stack.push(next[i]);
    }
  }
  return order;
}

Две неща са по-различни от рекурсията:

Спирка може да влезе в стека два пъти: от двама съседи, преди да е посетена. Затова проверката „видяна ли е“ е и при взимането: втория път се прескача.
Съседите влизат наобратно. Последният сложен излиза пръв, затова първият съсед трябва да е най-отгоре. Така редът е същият като при рекурсията:

const islandOf = new Map();
visit(graph, "Склад", 1, islandOf);
console.log(`Рекурсия: ${[...islandOf.keys()].join(", ")}`);
console.log(`Свой стек: ${walk(graph, "Склад").join(", ")}`);

Рекурсия: Склад, Гара, Площад, Пазар, Парк, Стадион, Болница, Кино
Свой стек: Склад, Гара, Площад, Пазар, Парк, Стадион, Болница, Кино

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

Ако сложиш съседите в реда на списъка, обходът пак е в дълбочина и пак намира същите острови, само редът на посещение е друг. За островите редът няма значение. За кръговете в насочен граф по-долу има: там трябва да знаеш кога свършва всяка спирка, а със стек от спирки това е по-трудно. Затова findCycle е рекурсивен, а при дълбоки графи в стека се слага двойка (спирка, докъде е стигнала в списъка си).

Идеята

Кръг в плана на доставките

Правилата на плана са насочен граф: стрелката Пазар → Парк значи „Пазар преди Парк“. Ако стрелките образуват кръг, няма ред, който да ги спазва: всяка спирка от кръга трябва да е преди себе си.

Само „видена“ не стига, за да хванеш кръг. Пазар → Площад води до видена спирка, но кръг няма: от Площад не се стига обратно до Пазар. Затова спирките имат три цвята:

бяла: още не е виждана;
сива: на текущия път, извикването ѝ още е отворено;
черна: всичко след нея е проверено и кръг няма.

Стрелка към сива спирка води обратно в собствения път: това е кръгът.

function findCycle(plan, stop, color, path) {
  color.set(stop, "grey");
  path.push(stop);
  for (const next of plan.get(stop)) {
    const c = color.get(next) ?? "white";
    if (c === "grey") {
      return [...path.slice(path.indexOf(next)), next];
    }
    if (c === "white") {
      const found = findCycle(plan, next, color, path);
      if (found !== null) return found;
    }
  }
  color.set(stop, "black");
  path.pop();
  return null;
}

function findCycle(plan, stop, color, path) {
  color.set(stop, "grey");
  path.push(stop);
  for (const next of plan.get(stop)) {
    const c = color.get(next) ?? "white";
    if (c === "grey") {
      return [...path.slice(path.indexOf(next)), next];
    }
    if (c === "white") {
      const found = findCycle(plan, next, color, path);
      if (found !== null) return found;
    }
  }
  color.set(stop, "black");
  path.pop();
  return null;
}

Стъпка по стъпка, с думи

Всяка стрелка е правило: спирката, от която излиза, се доставя първа. Всички спирки са бели, никой не е виждан. Обходът тръгва от Склад.
Сиво значи „на текущия път“: Склад → Гара → Площад. Тези извиквания още са отворени.
От Площад не излизат правила: почернява, всичко след нея е проверено и тя излиза от пътя. И Гара е готова.
И Пазар сочи към Площад, но Площад е черна: от нея няма път обратно до Пазар. Две правила към една спирка не са кръг.
Отвъд реката пътят расте: Парк → Кино → Болница → Стадион, всички сиви.
Стадион → Парк: Парк е сив, още е на пътя. Стрелката води обратно в самия път, а това е кръг.
Кръгът е пътят от Парк до края: Парк → Кино → Болница → Стадион → Парк. Никой ред на тези четири спирки не спазва всички правила, затова правилото Стадион → Парк трябва да отпадне.

Цикълът пуска findCycle от всяка бяла спирка, както islands пуска visit:

function anyCycle(plan, stops) {
  const color = new Map();
  for (const stop of stops) {
    if (color.has(stop)) continue;
    const found = findCycle(plan, stop, color, []);
    if (found !== null) return found;
  }
  return null;
}

const rules = [
  ["Склад", "Гара"], ["Гара", "Площад"],
  ["Склад", "Пазар"], ["Пазар", "Площад"],
  ["Пазар", "Парк"], ["Парк", "Кино"],
  ["Кино", "Болница"], ["Болница", "Стадион"],
  ["Стадион", "Парк"],
];

const cycle = anyCycle(plan, stops);
console.log(cycle === null ? "Няма кръг" : `Кръг: ${cycle.join(" → ")}`);

Кръг: Парк → Кино → Болница → Стадион → Парк

Махни последното правило, и програмата печата Няма кръг. Тогава редът, в който спирките почерняват, е обърнатият ред на доставките. На това стъпва топологичното сортиране, следващият урок.

function findCycle(plan, stop, color, path) {
  color.set(stop, "grey");
  path.push(stop);
  for (const next of plan.get(stop)) {
    const c = color.get(next) ?? "white";
    if (c === "grey") {
      return [...path.slice(path.indexOf(next)), next];
    }
    if (c === "white") {
      const found = findCycle(plan, next, color, path);
      if (found !== null) return found;
    }
  }
  color.set(stop, );
  path.pop();
  return null;
}

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

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

Идеята

Колко струва

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

Линейно е само ако номерът на острова е общ за целия обход. Ако за всяка спирка питаш „на кой остров съм?“ с нов обход и празно множество на видените, правиш n обхода. Пусни и двата върху град-решетка от n кръстовища, която реката реже на две:

Един общ islandOf за целия град O(n)
Нов обход за всяко кръстовище O(n²)

Алгоритъм	n = 10	n = 1000	n = 2000	n = 100 000
Един общ islandOf за целия град	28	4808	9730	498 100
Нов обход за всяко кръстовище	148	2 405 440	9 730 980	≈ 24 327 450 000

Кодът се пуска в твоя браузър на JavaScript. Броят операции е същият на всеки език, защото алгоритъмът е същият. Времето зависи от машината, затова е само за сравнение. „≈“ е оценка по кривата: толкова голямо n не пускаме, за да не замръзне страницата.

function islands(graph, stops) {
  const islandOf = new Map();
  let count = 0;
  for (const stop of stops) {
    if (islandOf.has(stop)) continue;
    count++;
    visit(graph, stop, count, islandOf);
  }
  return islandOf;
}

Броят се всяка спирка, взета от стека, и всеки поглед към съсед. И двата са със свой стек: при 100 000 кръстовища рекурсията в браузъра пада с препълнен стек. При 1000 кръстовища общият номер прави 4 808 операции, а новият обход за всяко кръстовище 2 405 440. При 2000 новият обход е вече 9 730 980, а общият при 100 000 прави 498 100.

Пробвай

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

Колега реши, че в visit островът трябва да расте с всяка стъпка. Програмата печата:

function visit(graph, stop, island, islandOf) {
  islandOf.set(stop, island);
  for (const next of graph.get(stop)) {
    if (!islandOf.has(next)) {
      visit(graph, next, island + 1, islandOf);
    }
  }
}

Острови: 5
Остров 1: Склад
Остров 2: Гара, Парк
Остров 3: Площад, Стадион
Остров 4: Пазар, Болница
Остров 5: Кино

Островите са пет, а Гара и Парк са „на един остров“, макар мостовете да са затворени. На кой ред е грешката?

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

По-точно

Колко дълбоко може рекурсията

Двигателите на JavaScript спират рекурсията на около 10 000 нива (зависи от браузъра и от размера на рамката) с RangeError: Maximum call stack size exceeded. Масивът с push и pop е стек с O(1) от края и няма такава граница.

Упражнение

Критичните улици

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

Критични улици. Мостът Пазар – Парк е затворен за месец, а Площад – Кино още работи. Улица е критична, ако затварянето ѝ разделя града на повече острови. Затвори моста, изведи колко острова има, после за всяка отворена улица я махни, преброй островите с islands и я върни. Изведи критичните улици в реда на streets.

const closed = [
  ["Пазар", "Парк"],
];

Острови: 1
Критични: Площад - Кино, Кино - Болница, Парк - Стадион, Болница - Стадион

Още задачи

Най-големият остров. Изведи острова с най-много спирки и колко бус-часа на седмица му трябват, ако всяка спирка иска 3 часа.
Кръгът в плана. Направи findCycle със свой стек: в стека слагай двойка (спирка, индекс на следващия съсед), а спирката почернява, когато индексът стигне края на списъка ѝ.
Острови на картата. Картата на склада е решетка от # (рафт) и . (свободно). Преброй свободните зони, като съседи на клетка са горе, долу, ляво и дясно.

Тест

Провери се

1. Какво прави DFS, когато около текущата спирка всичко вече е видяно?Спира целия обходТръгва отначало от складаВръща се към спирката, от която е дошъл, и опитва следващия ѝ съсед

2. Защо islands минава през всички спирки, а не пуска visit само от склада?Защото редът на спирките е важен за DFSЗа да провери дали visit работи правилноЕдин visit стига само до своя остров; спирките отвъд затворените мостове остават без номер

3. В насочения план findCycle вижда стрелка към черна спирка. Кръг ли е?Да: спирката вече е видянаНе: черната е проверена докрай и от нея няма път обратно до текущатаЗависи от реда на правилата

4. Градът има 100 000 кръстовища в една дълга верига. Какво става с рекурсивния visit?Нищо: рекурсията е бързаРаботи, но е O(V²)Дълбочината стига 100 000 извиквания и стекът се препълва; трябва свой стек

DFS: острови и кръгове

Бисквитки