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

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

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

Проблем

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

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

offices = ["Център", "Север", "Юг", "Изток", "Запад", "Летище"]
cables = [
    ("Център", "Север", 4),
    ("Център", "Юг", 6),
    ("Център", "Изток", 8),
    ("Център", "Запад", 5),
    ("Север", "Изток", 9),
    ("Север", "Запад", 3),
    ("Юг", "Запад", 7),
    ("Юг", "Летище", 11),
    ("Изток", "Летище", 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, без промяна. Кабелът е кортеж (офис, офис, цена), а index превежда името на офиса в номер, защото union-find работи с номера.

def kruskal(offices, cables):
    index = {o: i for i, o in enumerate(offices)}
    groups = UnionFind(len(offices))
    tree = []
    for a, b, cost in sorted(cables, key=lambda c: c[2]):
        if not groups.union(index[a], index[b]):
            continue  # цикъл
        tree.append((a, b, cost))
        if len(tree) == len(offices) - 1:
            break
    return tree
sorted с key=lambda c: c[2] подрежда по третия елемент, цената, и е стабилен.
total = 0
for a, b, cost in kruskal(offices, cables):
    print(f"{a} – {b}: {cost} хил. €")
    total += cost
print(f"Общо: {total} хил. €")
Изход
Изток – Летище: 2 хил. €
Север – Запад: 3 хил. €
Център – Север: 4 хил. €
Център – Юг: 6 хил. €
Център – Изток: 8 хил. €
Общо: 23 хил. €

def kruskal(offices, cables):
    index = {o: i for i, o in enumerate(offices)}
    groups = UnionFind(len(offices))
    tree = []
    for a, b, cost in sorted(cables, key=lambda c: c[2]):
        if not groups.union(index[a], index[b]):
            continue  # цикъл
        tree.append((a, b, cost))
        if len(tree) == len(offices) - 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. Каква е цената на новата мрежа?

changed = cables[:-1] + [("Изток", "Летище", 12)]
total = sum(cost for _, _, cost in kruskal(offices, changed))
print(f"Общо: {total} хил. €")
Отговор

Пробвай

Попълни

tree.append((a, b, cost))
if len(tree) == :
    break

Идеята

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

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

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

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

Пробвай

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

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

def kruskal(offices, cables):
    index = {o: i for i, o in enumerate(offices)}
    groups = UnionFind(len(offices))
    tree = []
    for a, b, cost in sorted(cables, key=lambda c: c[2]):
        if groups.find(index[a]) == groups.find(index[b]):
            continue
        tree.append((a, b, cost))
        if len(tree) == len(offices) - 1:
            break
    return tree
total = 0
for a, b, cost in kruskal(offices, cables):
    print(f"{a} – {b}: {cost} хил. €")
    total += cost
print(f"Общо: {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 по вече положените кабели:

def connected(net, start, goal):
    stack = [start]
    seen = {start}
    while stack:
        office = stack.pop()
        if office == goal:
            return True
        for other in net[office]:
            if other not in seen:
                seen.add(other)
                stack.append(other)
    return False




def kruskal_slow(offices, cables):
    net = {office: [] for office in offices}
    tree = []
    for a, b, cost in sorted(cables, key=lambda c: c[2]):
        if connected(net, a, b):
            continue
        net[a].append(b)
        net[b].append(a)
        tree.append((a, b, cost))
        if len(tree) == len(offices) - 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 не пускаме, за да не замръзне страницата.
def kruskal(offices, cables):
    index = {o: i for i, o in enumerate(offices)}
    groups = UnionFind(len(offices))
    tree = []
    for a, b, cost in sorted(cables, key=lambda c: c[2]):
        if not groups.union(index[a], index[b]):
            continue  # цикъл
        tree.append((a, b, cost))
        if len(tree) == len(offices) - 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 за достъпно обучение по програмиране ·