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

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

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

Проблем

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

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

List<String> offices = List.of("Център", "Север", "Юг", "Изток", "Запад", "Летище");
List<Cable> cables = List.of(
        new Cable("Център", "Север", 4),
        new Cable("Център", "Юг", 6),
        new Cable("Център", "Изток", 8),
        new Cable("Център", "Запад", 5),
        new Cable("Север", "Изток", 9),
        new Cable("Север", "Запад", 3),
        new Cable("Юг", "Запад", 7),
        new Cable("Юг", "Летище", 11),
        new Cable("Изток", "Летище", 2));

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

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

Идеята

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

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

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

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

Виж го

Kruskal отвътре

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

static List<Cable> kruskal(
        List<String> offices, List<Cable> cables) {
    Map<String, Integer> index = new HashMap<>();
    for (String o : offices) index.put(o, index.size());
    List<Cable> sorted = new ArrayList<>(cables);
    sorted.sort(Comparator.comparingInt(Cable::cost));
    var groups = new UnionFind(offices.size());
    List<Cable> tree = new ArrayList<>();
    for (Cable c : sorted) {
        int a = index.get(c.from());
        int b = index.get(c.to());
        if (!groups.union(a, b)) continue; // цикъл
        tree.add(c);
        if (tree.size() == offices.size() - 1) break;
    }
    return tree;
}
sort с Comparator.comparingInt(Cable::cost) е стабилен: кабели с еднаква цена остават в реда си.
int total = 0;
for (Cable c : kruskal(offices, cables)) {
    System.out.println(c.from() + " – " + c.to() + ": " + c.cost() + " хил. €");
    total += c.cost();
}
System.out.println("Общо: " + total + " хил. €");
Изход
Изток – Летище: 2 хил. €
Север – Запад: 3 хил. €
Център – Север: 4 хил. €
Център – Юг: 6 хил. €
Център – Изток: 8 хил. €
Общо: 23 хил. €

static List<Cable> kruskal(
        List<String> offices, List<Cable> cables) {
    Map<String, Integer> index = new HashMap<>();
    for (String o : offices) index.put(o, index.size());
    List<Cable> sorted = new ArrayList<>(cables);
    sorted.sort(Comparator.comparingInt(Cable::cost));
    var groups = new UnionFind(offices.size());
    List<Cable> tree = new ArrayList<>();
    for (Cable c : sorted) {
        int a = index.get(c.from());
        int b = index.get(c.to());
        if (!groups.union(a, b)) continue; // цикъл
        tree.add(c);
        if (tree.size() == offices.size() - 1) break;
    }
    return tree;
}
Стъпка по стъпка, с думи
  1. Шест офиса, девет възможни кабела, всеки с цена в хиляди евро. Мрежата трябва да свърже всички офиси възможно най-евтино. Вдясно кабелите се подреждат по цена: Kruskal ги гледа от най-евтиния. Отначало всеки офис е отделна група.
  2. Изток – Летище, 2: различни групи. Кабелът се полага, а union слива двете групи в една (един цвят).
  3. Север – Запад, 3: пак различни групи. Появява се втора, отделна група: Kruskal строи няколко парчета наведнъж, а не едно дърво, което расте.
  4. Център – Север, 4: Център влиза в групата на Север и Запад.
  5. Център – Запад, 5: двата края вече са в една група, през Север. Този кабел би затворил цикъл: union връща false и кабелът се отхвърля.
  6. Център – Юг, 6: Юг е сам, затова кабелът се полага.
  7. Юг – Запад, 7: Юг и Запад вече са свързани през Център. Отхвърлен.
  8. Център – Изток, 8: най-евтиният кабел между двете групи. Слива ги, и кабелите вече са пет: шест офиса, пет кабела, всичко е свързано.
  9. Цикълът спира: Север – Изток и Юг – Летище изобщо не се поглеждат. Общо 23 хил. €, срещу 55 за всичките девет кабела.

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

Пробвай

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

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

List<Cable> changed = new ArrayList<>(cables);
changed.set(changed.size() - 1, new Cable("Изток", "Летище", 12));
int total = kruskal(offices, changed).stream().mapToInt(Cable::cost).sum();
System.out.println("Общо: " + total + " хил. €");
Отговор

Пробвай

Попълни

tree.add(c);
if (tree.size() == ) break;

Идеята

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

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

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

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

Пробвай

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

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

static List<Cable> kruskal(
        List<String> offices, List<Cable> cables) {
    Map<String, Integer> index = new HashMap<>();
    for (String o : offices) index.put(o, index.size());
    List<Cable> sorted = new ArrayList<>(cables);
    sorted.sort(Comparator.comparingInt(Cable::cost));
    var groups = new UnionFind(offices.size());
    List<Cable> tree = new ArrayList<>();
    for (Cable c : sorted) {
        int a = index.get(c.from());
        int b = index.get(c.to());
        if (groups.find(a) == groups.find(b)) continue;
        tree.add(c);
        if (tree.size() == offices.size() - 1) break;
    }
    return tree;
}
int total = 0;
for (Cable c : kruskal(offices, cables)) {
    System.out.println(c.from() + " – " + c.to() + ": " + c.cost() + " хил. €");
    total += c.cost();
}
System.out.println("Общо: " + 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 по вече положените кабели:

static boolean connected(Map<String, List<String>> net, String from, String to) {
    Deque<String> stack = new ArrayDeque<>(List.of(from));
    Set<String> seen = new HashSet<>(List.of(from));
    while (!stack.isEmpty()) {
        String office = stack.pop();
        if (office.equals(to)) return true;
        for (String next : net.get(office)) {
            if (seen.add(next)) stack.push(next);
        }
    }
    return false;
}


static List<Cable> kruskalSlow(List<String> offices, List<Cable> cables) {
    Map<String, List<String>> net = new HashMap<>();
    for (String office : offices) net.put(office, new ArrayList<>());
    List<Cable> sorted = new ArrayList<>(cables);
    sorted.sort(Comparator.comparingInt(Cable::cost));
    List<Cable> tree = new ArrayList<>();
    for (Cable c : sorted) {
        if (connected(net, c.from(), c.to())) continue;
        net.get(c.from()).add(c.to());
        net.get(c.to()).add(c.from());
        tree.add(c);
        if (tree.size() == offices.size() - 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 = 100n = 1000n = 10 000n = 100 000
Kruskal с DFS: търсене по положените кабели4945677 351≈ 67 735 100≈ 6 773 510 000
Kruskal с union-find146023 827321 1713 884 598
Кодът се пуска в твоя браузър на JavaScript. Броят операции е същият на всеки език, защото алгоритъмът е същият. Времето зависи от машината, затова е само за сравнение. „≈“ е оценка по кривата: толкова голямо n не пускаме, за да не замръзне страницата.
static List<Cable> kruskal(
        List<String> offices, List<Cable> cables) {
    Map<String, Integer> index = new HashMap<>();
    for (String o : offices) index.put(o, index.size());
    List<Cable> sorted = new ArrayList<>(cables);
    sorted.sort(Comparator.comparingInt(Cable::cost));
    var groups = new UnionFind(offices.size());
    List<Cable> tree = new ArrayList<>();
    for (Cable c : sorted) {
        int a = index.get(c.from());
        int b = index.get(c.to());
        if (!groups.union(a, b)) continue; // цикъл
        tree.add(c);
        if (tree.size() == offices.size() - 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 офиса възможно най-евтино. Колко кабела има в нея?
2. Kruskal стига до кабел, чиито два края вече са в една група. Какво прави?
3. Защо Kruskal ползва union-find, а не търсене (DFS) по положените кабели?
4. В минималното покриващо дърво пътят от Юг до Летище е през Център и Изток, 16 хил. €. Директният кабел Юг – Летище е 11. Значи ли това, че дървото е сгрешено?

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