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

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

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

Проблем

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

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

var offices = new List<string> { "Център", "Север", "Юг", "Изток", "Запад", "Летище" };
var cables = new List<Cable>
{
    new("Център", "Север", 4),
    new("Център", "Юг", 6),
    new("Център", "Изток", 8),
    new("Център", "Запад", 5),
    new("Север", "Изток", 9),
    new("Север", "Запад", 3),
    new("Юг", "Запад", 7),
    new("Юг", "Летище", 11),
    new("Изток", "Летище", 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)
{
    var index = new Dictionary<string, int>();
    foreach (string o in offices) index[o] = index.Count;
    var sorted = cables.OrderBy(c => c.Cost).ToList();
    var groups = new UnionFind(offices.Count);
    var tree = new List<Cable>();
    foreach (Cable c in sorted)
    {
        int a = index[c.From];
        int b = index[c.To];
        if (!groups.Union(a, b)) continue; // цикъл
        tree.Add(c);
        if (tree.Count == offices.Count - 1) break;
    }
    return tree;
}
OrderBy е стабилен: кабели с еднаква цена остават в реда си. ToList() го изпълнява веднага.
int total = 0;
foreach (Cable c in Kruskal(offices, cables))
{
    Console.WriteLine($"{c.From} – {c.To}: {c.Cost} хил. €");
    total += c.Cost;
}
Console.WriteLine($"Общо: {total} хил. €");
Изход
Изток – Летище: 2 хил. €
Север – Запад: 3 хил. €
Център – Север: 4 хил. €
Център – Юг: 6 хил. €
Център – Изток: 8 хил. €
Общо: 23 хил. €

static List<Cable> Kruskal(
    List<string> offices, List<Cable> cables)
{
    var index = new Dictionary<string, int>();
    foreach (string o in offices) index[o] = index.Count;
    var sorted = cables.OrderBy(c => c.Cost).ToList();
    var groups = new UnionFind(offices.Count);
    var tree = new List<Cable>();
    foreach (Cable c in sorted)
    {
        int a = index[c.From];
        int b = index[c.To];
        if (!groups.Union(a, b)) continue; // цикъл
        tree.Add(c);
        if (tree.Count == offices.Count - 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. Каква е цената на новата мрежа?

var changed = new List<Cable>(cables);
changed[^1] = new("Изток", "Летище", 12);
int total = Kruskal(offices, changed).Sum(c => c.Cost);
Console.WriteLine($"Общо: {total} хил. €");
Отговор

Пробвай

Попълни

tree.Add(c);
if (tree.Count == ) break;

Идеята

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

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

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

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

Пробвай

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

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

static List<Cable> Kruskal(
    List<string> offices, List<Cable> cables)
{
    var index = new Dictionary<string, int>();
    foreach (string o in offices) index[o] = index.Count;
    var sorted = cables.OrderBy(c => c.Cost).ToList();
    var groups = new UnionFind(offices.Count);
    var tree = new List<Cable>();
    foreach (Cable c in sorted)
    {
        int a = index[c.From];
        int b = index[c.To];
        if (groups.Find(a) == groups.Find(b)) continue;
        tree.Add(c);
        if (tree.Count == offices.Count - 1) break;
    }
    return tree;
}
int total = 0;
foreach (Cable c in Kruskal(offices, cables))
{
    Console.WriteLine($"{c.From} – {c.To}: {c.Cost} хил. €");
    total += c.Cost;
}
Console.WriteLine($"Общо: {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 bool Connected(Dictionary<string, List<string>> net, string from, string to)
{
    var stack = new Stack<string>();
    stack.Push(from);
    var seen = new HashSet<string> { from };
    while (stack.Count > 0)
    {
        string office = stack.Pop();
        if (office == to) return true;
        foreach (string next in net[office])
        {
            if (seen.Add(next)) stack.Push(next);
        }
    }
    return false;
}


static List<Cable> KruskalSlow(List<string> offices, List<Cable> cables)
{
    var net = offices.ToDictionary(office => office, _ => new List<string>());
    var tree = new List<Cable>();
    foreach (Cable c in cables.OrderBy(c => c.Cost))
    {
        if (Connected(net, c.From, c.To)) continue;
        net[c.From].Add(c.To);
        net[c.To].Add(c.From);
        tree.Add(c);
        if (tree.Count == offices.Count - 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)
{
    var index = new Dictionary<string, int>();
    foreach (string o in offices) index[o] = index.Count;
    var sorted = cables.OrderBy(c => c.Cost).ToList();
    var groups = new UnionFind(offices.Count);
    var tree = new List<Cable>();
    foreach (Cable c in sorted)
    {
        int a = index[c.From];
        int b = index[c.To];
        if (!groups.Union(a, b)) continue; // цикъл
        tree.Add(c);
        if (tree.Count == offices.Count - 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 за достъпно обучение по програмиране ·