Минимално покриващо дърво и Kruskal в JavaScript

Проблем

Най-евтината мрежа

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

const offices = ["Център", "Север", "Юг", "Изток", "Запад", "Летище"];
const cables = [
  { from: "Център", to: "Север", cost: 4 },
  { from: "Център", to: "Юг", cost: 6 },
  { from: "Център", to: "Изток", cost: 8 },
  { from: "Център", to: "Запад", cost: 5 },
  { from: "Север", to: "Изток", cost: 9 },
  { from: "Север", to: "Запад", cost: 3 },
  { from: "Юг", to: "Запад", cost: 7 },
  { from: "Юг", to: "Летище", cost: 11 },
  { from: "Изток", to: "Летище", cost: 2 },
];

Да положиш всичките девет кабела струва 55 хил. €. Но не трябват всички. Ако три офиса са свързани в кръг, единият кабел от кръга е излишен: махни го и всичко пак е свързано. Най-евтината мрежа няма нито един цикъл (cycle). Свързан граф без цикъл е дърво (tree), а дърво с V върха има точно V − 1 ребра: тук 5 кабела.

Кои пет? Търсиш дървото, което покрива всички офиси с най-малка обща цена. Това е минимално покриващо дърво (minimum spanning tree, MST).

Идеята

Най-евтиният кабел, който не затваря цикъл

Алгоритъмът на Kruskal (Джоузеф Крускал, 1956):

Подреди кабелите по цена, от най-евтиния.
За всеки кабел: ако двата му края още не са свързани, положи го. Ако вече са свързани през положени кабели, кабелът би затворил цикъл: прескочи го.
Спри, щом кабелите станат V − 1.

Отначало всеки офис е отделна група. Всеки положен кабел слива две групи в една. Въпросът „свързани ли са двата края“ е точно въпросът „в една група ли са“, а за него има структура: union-find. union(a, b) слива групите и връща false, ако a и b вече са в една група. Една проверка вместо търсене по картата.

Виж го

Kruskal отвътре

Класът UnionFind е същият като в урока за union-find, без промяна. Кабелът е обект с from, to и cost, а index превежда името на офиса в номер, защото union-find работи с номера.

function kruskal(offices, cables) {
  const index = new Map(offices.map((o, i) => [o, i]));
  const sorted = [...cables].sort((x, y) => x.cost - y.cost);
  const groups = new UnionFind(offices.length);
  const tree = [];
  for (const c of sorted) {
    const a = index.get(c.from);
    const b = index.get(c.to);
    if (!groups.union(a, b)) continue; // цикъл
    tree.push(c);
    if (tree.length === offices.length - 1) break;
  }
  return tree;
}

sort подрежда масива на място, затова първо копираш cables с [...cables]. Сравнението връща отрицателно число, ако x е по-евтин.

let total = 0;
for (const c of kruskal(offices, cables)) {
  console.log(`${c.from} – ${c.to}: ${c.cost} хил. €`);
  total += c.cost;
}
console.log(`Общо: ${total} хил. €`);

Изток – Летище: 2 хил. €
Север – Запад: 3 хил. €
Център – Север: 4 хил. €
Център – Юг: 6 хил. €
Център – Изток: 8 хил. €
Общо: 23 хил. €

function kruskal(offices, cables) {
  const index = new Map(offices.map((o, i) => [o, i]));
  const sorted = [...cables].sort((x, y) => x.cost - y.cost);
  const groups = new UnionFind(offices.length);
  const tree = [];
  for (const c of sorted) {
    const a = index.get(c.from);
    const b = index.get(c.to);
    if (!groups.union(a, b)) continue; // цикъл
    tree.push(c);
    if (tree.length === offices.length - 1) break;
  }
  return tree;
}

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

Шест офиса, девет възможни кабела, всеки с цена в хиляди евро. Мрежата трябва да свърже всички офиси възможно най-евтино. Вдясно кабелите се подреждат по цена: Kruskal ги гледа от най-евтиния. Отначало всеки офис е отделна група.
Изток – Летище, 2: различни групи. Кабелът се полага, а union слива двете групи в една (един цвят).
Север – Запад, 3: пак различни групи. Появява се втора, отделна група: Kruskal строи няколко парчета наведнъж, а не едно дърво, което расте.
Център – Север, 4: Център влиза в групата на Север и Запад.
Център – Запад, 5: двата края вече са в една група, през Север. Този кабел би затворил цикъл: union връща false и кабелът се отхвърля.
Център – Юг, 6: Юг е сам, затова кабелът се полага.
Юг – Запад, 7: Юг и Запад вече са свързани през Център. Отхвърлен.
Център – Изток, 8: най-евтиният кабел между двете групи. Слива ги, и кабелите вече са пет: шест офиса, пет кабела, всичко е свързано.
Цикълът спира: Север – Изток и Юг – Летище изобщо не се поглеждат. Общо 23 хил. €, срещу 55 за всичките девет кабела.

Две групи растат отделно: синята (Изток, Летище) и зелената, която започва от Север и Запад. Кабелът Център – Изток е най-евтиният между тях и ги слива. Кабелите Север – Изток (9) и Юг – Летище (11) изобщо не се поглеждат.

Пробвай

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

Магистралата до летището се оказва проблем: кабелът Изток – Летище вече струва 12. Каква е цената на новата мрежа?

const changed = [...cables.slice(0, -1), { from: "Изток", to: "Летище", cost: 12 }];
const total = kruskal(offices, changed).reduce((sum, c) => sum + c.cost, 0);
console.log(`Общо: ${total} хил. €`);

Отговор

Общо: 30 хил. €

Общо: 32 хил. €

Общо: 33 хил. €

Пробвай

Попълни

tree.push(c);
if (tree.length === ) break;

Идеята

Защо алчното тук е вярно

Kruskal е алчен алгоритъм: на всяка стъпка взима най-доброто сега (най-евтиния кабел, който става) и не се връща назад. Често алчното лъже: виж кога алчното работи и кога не работи. Тук работи, и причината е свойството на среза (cut property).

Раздели офисите на две части по какъвто и да е начин, например групата на Изток и всички останали. Кабелите, които минават между двете части, са срезът. Най-евтиният кабел в среза е в минималното дърво. Защо? Дървото трябва да има поне един кабел през среза, иначе двете части не са свързани. Ако е по-скъп, смени го с най-евтиния: мрежата пак е свързана, а цената пада.

Всеки кабел, който Kruskal слага, е най-евтиният в среза между групата на единия му край и всичко останало: всички по-евтини кабели вече са минали и са вътре в групи. Център – Изток (8) е най-евтиният от Център – Изток, Север – Изток (9) и Юг – Летище (11), кабелите между двете групи.

Пробвай

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

Колега реши, че union е излишен, и само пита find дали двата края са в една група:

function kruskal(offices, cables) {
  const index = new Map(offices.map((o, i) => [o, i]));
  const sorted = [...cables].sort((x, y) => x.cost - y.cost);
  const groups = new UnionFind(offices.length);
  const tree = [];
  for (const c of sorted) {
    const a = index.get(c.from);
    const b = index.get(c.to);
    if (groups.find(a) === groups.find(b)) continue;
    tree.push(c);
    if (tree.length === offices.length - 1) break;
  }
  return tree;
}

let total = 0;
for (const c of kruskal(offices, cables)) {
  console.log(`${c.from} – ${c.to}: ${c.cost} хил. €`);
  total += c.cost;
}
console.log(`Общо: ${total} хил. €`);

Изток – Летище: 2 хил. €
Север – Запад: 3 хил. €
Център – Север: 4 хил. €
Център – Запад: 5 хил. €
Център – Юг: 6 хил. €
Общо: 20 хил. €

20 хил. € вместо 23, но Изток и Летище са отрязани, а Център, Север и Запад са в кръг. На кой ред е грешката?

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

Идеята

Колко струва

Подреждането на E кабела е O(E log E). След него всяка проверка с union-find е почти O(1) (виж урока за union-find). Общо O(E log E): подреждането е по-скъпото.

Без union-find „свързани ли са“ се пита с DFS по вече положените кабели:

function connected(net, from, to) {
  const stack = [from];
  const seen = new Set([from]);
  while (stack.length > 0) {
    const office = stack.pop();
    if (office === to) return true;
    for (const next of net.get(office)) {
      if (!seen.has(next)) {
        seen.add(next);
        stack.push(next);
      }
    }
  }
  return false;
}

function kruskalSlow(offices, cables) {
  const net = new Map(offices.map((office) => [office, []]));
  const sorted = [...cables].sort((x, y) => x.cost - y.cost);
  const tree = [];
  for (const c of sorted) {
    if (connected(net, c.from, c.to)) continue;
    net.get(c.from).push(c.to);
    net.get(c.to).push(c.from);
    tree.push(c);
    if (tree.length === offices.length - 1) break;
  }
  return tree;
}

Отговорът е същият. Но всяко търсене може да обходи цялата група, O(V), и се прави за всеки кабел: O(E · V).

Пусни двата варианта на мрежа от офиси в решетка: всеки офис може да се свърже с десния и долния си съсед, с цена от 1 до 1000. Брои се всяко сравнение на две цени при подреждането, всеки огледан съсед при DFS и всяка стъпка към родител при find.

Kruskal с DFS: търсене по положените кабели O(n²)
Kruskal с union-find O(n log n)

Алгоритъм	n = 100	n = 1000	n = 10 000	n = 100 000
Kruskal с DFS: търсене по положените кабели	4945	677 351	≈ 67 735 100	≈ 6 773 510 000
Kruskal с union-find	1460	23 827	321 171	3 884 598

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

function kruskal(offices, cables) {
  const index = new Map(offices.map((o, i) => [o, i]));
  const sorted = [...cables].sort((x, y) => x.cost - y.cost);
  const groups = new UnionFind(offices.length);
  const tree = [];
  for (const c of sorted) {
    const a = index.get(c.from);
    const b = index.get(c.to);
    if (!groups.union(a, b)) continue; // цикъл
    tree.push(c);
    if (tree.length === offices.length - 1) break;
  }
  return tree;
}

При 1000 офиса с DFS са 677 351 стъпки, с union-find 23 827. При 100 000 офиса union-find прави 3 884 598, а DFS би направил милиарди: Bench не ги пуска, а ги оценява по кривата.

Идеята

Не е най-краткият път

В минималното дърво пътят от Юг до Летище е Юг – Център – Изток – Летище: 6 + 8 + 2 = 16. Директният кабел Юг – Летище е 11, но той не е в мрежата.

Минималното покриващо дърво пести общата цена на мрежата. Не обещава нищо за пътя между два офиса. Ако цената е закъснение и искаш най-бързия път между два офиса, това е друга задача: Dijkstra.

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

Prim е другият класически алгоритъм за минимално покриващо дърво. Тръгва от един офис и всеки път добавя най-евтиния кабел от дървото към офис извън него. Опашката е приоритетна, както в Dijkstra, само че приоритетът е цената на кабела, а не пътят от началото. С двоичен heap е O(E log V). Kruskal е по-прост, когато кабелите са списък, а Prim, когато графът е даден със съседи и е гъст.

Ако има кабели с еднаква цена, минималните дървета може да са няколко, всичките с една и съща обща цена. Kruskal връща едно от тях, според реда на равните.

Къде още: електрическа и водопроводна мрежа, пътища между села, печатни платки. Ако спреш Kruskal, преди групите да станат една (например при k групи), получаваш групиране (clustering): точките в една група са близки, а групите са далеч една от друга.

Упражнение

Вече положен кабел

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

Стар кабел. Между Север и Изток вече има положен кабел: не струва нищо. Напиши метод, който приема и положените кабели и намира кои нови да се сложат. Изведи положените и новите кабели и цената на новите:

Вече положен: Север – Изток
Изток – Летище: 2 хил. €
Север – Запад: 3 хил. €
Център – Север: 4 хил. €
Център – Юг: 6 хил. €
Нови кабели: 15 хил. €

Подсказка: преди цикъла слей в union-find краищата на положените кабели. Спри, щом групата е една.

Още задачи

Отхвърлените. Изведи и отхвърлените кабели, всеки с причината: кой цикъл би затворил.
Две мрежи. Фирмата иска две отделни мрежи. Спри Kruskal, когато групите станат две. Кои офиси са в една мрежа?
Невъзможно. Махни всички кабели до Летище. Какво връща Kruskal? Как разбираш, че мрежата не свързва всички офиси?

Тест

Провери се

1. Мрежа свързва 6 офиса възможно най-евтино. Колко кабела има в нея?5Зависи от цените6

2. Kruskal стига до кабел, чиито два края вече са в една група. Какво прави?Прескача го: би затворил цикълСпира: мрежата е готоваСлага го, ако е по-евтин от досегашните

3. Защо Kruskal ползва union-find, а не търсене (DFS) по положените кабели?Проверката „свързани ли са“ става почти O(1), а не O(V)Защото DFS дава грешен отговорЗащото union-find подрежда кабелите

4. В минималното покриващо дърво пътят от Юг до Летище е през Център и Изток, 16 хил. €. Директният кабел Юг – Летище е 11. Значи ли това, че дървото е сгрешено?Да: трябва да е 11Да: Kruskal пропуска кабела с цена 11Не: то минимизира общата цена, а не пътя между два офиса

Минимално покриващо дърво

Бисквитки