алгоритм Круськала
Алгоритм Прима будує мінімальний кістяк по одному ребру, знаходячи на кожному кроці ребро, яке приєднується до єдиного зростаючому дереву. Алгоритм Круськала також будує MST, додаючи до нього по одному ребру, але на відміну від алгоритму Прима, він відшукує ребро, яке з'єднує два дерева в лісі, утвореному зростаючими MST-піддеревами. Побудова починається з виродженого лісу з V дерев (кожне складається з однієї вершини), а потім виконується операція об'єднання двох дерев (найкоротшими ребрами), поки не залишиться єдине дерево - MST.
на Мал. 20.12 показаний приклад покрокового виконання алгоритму Круськала; Мал. 20.13 демонструє динамічні характеристики цього алгоритму на більшому прикладі. Роз'єднаний ліс MST-піддерев поступово об'єднується в єдине дерево.
Мал.20.12.
Алгоритм Круськала обчислення MST
Нехай заданий список ребер графа в довільному порядку (лівий список ребер). На першому кроці алгоритму Круськала вони сортуються за вагами (правий список ребер). Потім ми переглядаємо ребра цього списку в порядку зростання їх ваг, додаючи в MST ребра, які не створюють в ньому циклів. Спочатку ми додаємо ребро 5-3 (найкоротший ребро), потім 7-6 (зліва), потім 0-2 (справа вгорі) і 0-7 (праворуч, друга діаграма зверху). Ребро 0-1 з наступним за величиною вагою створює цикл і тому не додається в дерево. Ребра, які не включаються до MST, виділені в відсортованому списку сірим кольором. Потім ми додаємо ребро 4-3 (праворуч, третя діаграма зверху). Далі ми відкидаємо ребро 5-4, оскільки воно утворює цикл, і потім додаємо 7-4 (справа внизу). Коли MST-дерево готове, будь ребро з великою вагою утворює цикл і тому буде відкинуто (алгоритм зупиняється, коли в MST будуть включені V- 1 ребер). У відсортованому списку ці ребра помічені зірочками.
Ребра додаються в MST-дерево в порядку зростання їх довжини - таким чином, ліс містить вершини, з'єднані один з одним відносно короткими ребрами. У будь-який момент виконання алгоритму кожна вершина розташована ближче до деякої вершини свого поддерева, ніж до будь-якої іншої вершини, що не входить в це дерево.
Алгоритм Круськала простий в реалізації - при наявності базових алгоритмічних інструментів, розглянутих раніше в даній книзі. Можна використовувати будь-яку сортування з описаних в частині 3 для упорядкування ребер по вазі і будь-який з алгоритмів розв'язання задачі зв'язності з "Вступ" для видалення ціклообразующіх ребер. Програма 20.8 містить відповідну реалізацію функції побудови MST для АТД графа, яка функціонально еквівалентна іншим реалізаціям MST, розглянутим в цьому розділі. Ця реалізація не залежить від уявлення графа: вона викликає клієнтську програму GRAPH, щоб отримати вектор, що містить ребра графа, а потім на основі цього вектора будує MST-дерево.
Зверніть увагу, що існують два способи закінчення роботи алгоритму Круськала. Якщо ми знайдемо V- 1 ребер, то ми вже побудували кістяк і можемо зупинитися. Якщо ми переглянемо все вершини і не знайдемо V- 1 деревних ребер, то це означає, що граф не є зв'язковим - точно так само, як це зроблено в "Вступ" .
Мал.20.13.
Алгоритм Круськала обчислення MST
Ця послідовність показує 1/4, 1/2, 3/4 і повне MST в міру його зростання.
Програма 20.8. Алгоритм Круськала обчислення MST
Для відшукання MST ця реалізація використовує АТД сортування з "Елементарні методи сортування" і АТД об'єднання-пошуку з "Абстрактні типи даних" , Розглядаючи ребра в порядку зростання їх ваг і відкидаючи ті ребра, які утворюють цикли, поки не будуть знайдені V- 1 вершин, що становлять кістяк.
Тут не показаний клас-оболонка EdgePtr, що дозволяє функції sort порівнювати покажчики на ребра за допомогою перевантаженої операції <, як описано в "Елементарні методи сортування" , І варіант програми 20.2 з третім шаблонним аргументом.
template <class Graph, class Edge, class EdgePtr> class MST {const Graph & G; vector <EdgePtr> a, mst; UF uf; public: MST (Graph & G): G (G), uf (GV ()), mst (GV ()) {int V = GV (), E = GE (); a = edges <Graph, Edge, EdgePtr> (G); sort <EdgePtr> (a, 0, E-1); for (int i = 0, k = 1; i <E && k <V; i ++) if (! uf.find (a [i] -> v, a [i] -> w)) {uf.unite ( a [i] -> v, a [i] -> w); mst [k ++] = a [i]; }}};
Аналіз часу виконання алгоритму Круськала не представляє труднощів, тому що відомий час виконання складових його операцій АТД.
Лемма 20.9. Алгоритм Круськала обчислює MST-дерево графа за час, пропорційне ElgE.
Доведення. Ця лема є наслідком більш загального факту: час виконання програми 20.8 пропорційно витратам на сортування E чисел плюс витрат на виконання E операцій знайти і V- 1 операцій об'єднати. Якщо використовувати стандартні реалізації АТД, такі як сортування злиттям і зважений алгоритм пошуку-об'єднання з розподілом навпіл, то основні витрати припадають на сортування. 
Порівняння продуктивності алгоритмів Круськала і Прима буде виконано в розділі 20.6. А поки врахуйте, що час виконання, пропорційне E lgE, не обов'язково гірше, ніж ElgV: тому що E не перевищує V2, то lgE не перевищує 2 lgV Відмінності в продуктивності для конкретних графів обумовлені особливостями реалізації і тим, наближається чи фактичний час виконання до граничним значенням для гіршого випадку.
На практиці можна скористатися швидким сортуванням або швидкої системної сортуванням (яка зазвичай заснована на швидкій сортування). Теоретично такий підхід може бути непривабливим через квадратичної трудомісткості сортування в гіршому випадку, однак зазвичай при цьому час виконання зменшується. Хоча взагалі-то можна скористатися поразрядной сортуванням, щоб виконати впорядкування ребер за лінійний час (при певних обмеженнях на ваги ребер) - тоді будуть превалювати витрати на виконання E операцій знайти. Це дозволить змінити формулювання леми 20.9: при виконанні заданих обмежень на ваги ребер час виконання алгоритму Круськала не перевищує 
з деяким постійним коефіцієнтом (див. "Принципи аналізу алгоритмів" ). Нагадаємо, що функція 
дорівнює кількості ітерацій двійковій логарифмічною функції, перш ніж результат стане менше одиниці; це значення менше 5, якщо E менше 265536. Тобто таке коригування робить алгоритм Круськала по суті лінійним в більшості практичних ситуацій.
Зазвичай трудомісткість обчислення MST за допомогою алгоритму Круськала навіть менше вартості обробки всіх ребер, оскільки побудова завершується задовго до того, як буде переглянута значна частина всіх ребер (довгого) графа. Цей факт дозволяє істотно зменшити час виконання в багатьох практичних ситуаціях, якщо взагалі не включати в сортування все ребра, довжина яких перевищує довжину найдовшого ребра MST. Один з найпростіших способів досягнення цієї мети - використання черзі з пріоритетами, в реалізації якої є операція створити з лінійним часом виконання і операція витягти мінімальне з логарифмічним часом.
Наприклад, таких характеристик продуктивності можна досягти за допомогою стандартної реалізації пірамідального дерева, використовуючи висхідний побудова (див. "Черги з пріоритетами і пірамідальна сортування" ). При цьому в програму 20.8 потрібно внести наступні зміни: виклик sort замінити викликом pq.construct (), щоб будувати пірамідальне дерево за час, пропорційне E, додати у внутрішній цикл відбір з черги з пріоритетами найкоротших ребер, для яких e = pq.delmin (), і замінити всі звернення до a [i] на e.
Лемма 20.10. Варіант алгоритму Круськала на основі черги з пріоритетами обчислює MST графа за час, пропорційне E + X lgV, де X - кількість ребер графа, що не перевищують по довжині найдовше ребро в MST.
Доведення. Наведене вище міркування показує, що трудомісткість алгоритму складається з витрат на побудову черзі з пріоритетами розміром E плюс вартість виконання X операцій витягти мінімальне, X операцій знайти і V- 1 операцій об'єднати. Зверніть увагу, що якщо X не більш E / lgV, то основна частка витрат припадає на побудову черзі з пріоритетами (а алгоритм лине по часу).
Ця ж ідея дозволяє отримати аналогічні переваги і в реалізації на основі швидкого сортування. Розглянемо, що станеться, якщо використовувати пряму рекурсивную швидку сортування, де виконується розбивка по i-му елементу з подальшою рекурсивної сортуванням подфайла зліва від i і подфайла праворуч від i. В силу побудови алгоритму після завершення першого рекурсивного виклику перші i елементів вже впорядковані (див. Програму 9.2). Цей очевидний факт дозволяє отримати швидку реалізацію алгоритму Круськала: якщо помістити перевірку, чи породжує ребро a [i] цикл, між рекурсивними викликами, то вийде алгоритм, який, з побудови, після завершення першого рекурсивного виклику вже перевірив перші i ребер (в порядку зростання ваг)! Якщо додати перевірку на припинення роботи після виявлення V- 1 ребер MST-дерева, то виходить алгоритм, який сортує лише стільки ребер, скільки їх необхідно для обчислення MST-дерева, плюс кілька додаткових етапів розбиття за участю великих елементів (див. Вправу 20.57) . Як і у випадку простих реалізацій сортування, цей алгоритм може зажадати квадратичного часу виконання в гіршому випадку, однак є імовірнісна гарантія того, що час виконання в гіршому випадку не буде близьким до такої межі. Крім того, подібно простим реалізаціям сортування, ця програма через більш короткого внутрішнього циклу зазвичай працює швидше реалізації на основі пірамідального дерева.
Якщо ж граф не є зв'язковим, то версія алгоритму Круськала на основі часткової сортування не дає ніяких переваг, оскільки в цьому випадку доводиться переглядати всі ребра графа. Навіть в разі зв'язкового графа найдовше ребро може виявитися в MST-дереві, і тоді будь-яка реалізація методу Круськала повинна переглянути всі ребра. Наприклад, граф може складатися з щільних кластерів вершин, з'єднаних всередині короткими ребрами, і тільки одна з вершин кластера з'єднана з "зовнішньої" вершиною довгим ребром. Незважаючи на можливість таких нетипових варіантів, підхід із застосуванням часткової сортування вартий уваги, оскільки дає суттєвий виграш і не вимагає великих додаткових витрат (або зовсім ніяких).
Цікаві й повчальні та історичні відомості. Круськала запропонував свій алгоритм в 1956 р, проте, знову-таки, протягом багатьох років не були докладно вивчені відповідні реалізації АТД. Тому наведені цифри щодо реалізацій, таких як версія програми 20.8 з чергою з пріоритетами, не отримали належної оцінки аж до 1970-х років. Ще один цікавий історичний факт: в статті Круськала згадувалася версія алгоритму Прима (див. Вправу 20.59), а Борувка описав у своїй статті обидва ці підходи. Ефективні реалізації методу Круськала для розріджених графів з'явилися раніше реалізацій методу Прима для розріджених графів - бо АТД пошуку-об'єднання (і сортування) стали застосовуватися раніше, ніж АТД черзі з пріоритетами. По суті, прогрес в сучасному стані алгоритму Круськала, як і реалізації алгоритму Прима, обумовлений головним чином підвищенням продуктивності АТД. З іншого боку, можливість застосування абстракції пошуку-об'єднання в алгоритмі Круськала і можливість застосування абстракції черзі з пріоритетами в алгоритмі Прима стали для багатьох дослідників основним стимулом для пошуку більш досконалих реалізацій цих АТД.
вправи
20.53. Покажіть в стилі Мал. 20.12 результат обчислення алгоритмом Круськала MST-дерева для мережі, визначеної у вправі 20.26.
20.54. Емпірично визначте для різних видів зважених графів довжину найдовшого ребра MST-дерева і кількість ребер графа, довжина яких становить менше довжини цього ребра (див. Вправи 20.9-20.14).
20.55. Розробіть реалізацію АТД об'єднання-пошуку, в якій операція знайти виконується за постійне час, а операція об'єднати - за час, пропорційне lgV.
20.56. Емпірично порівняйте для різних видів зважених графів реалізацію АТД з вправи 20.55 зі зваженим об'єднанням-пошуком з розподілом навпіл (програма 1.4), коли алгоритм Круськала є клієнтською програмою (див. Вправи 20.9-20.14). Виділіть витрати на сортування ребер окремо, щоб можна було вивчати вплив заміни на загальні витрати і на частину витрат, пов'язаних з АТД об'єднання-пошуку.
20.57. Розробіть реалізацію на основі описаної в тексті ідеї: інтеграції алгоритму Круськала з швидким сортуванням, щоб перевіряти кожне ребро на приналежність MST-дереву відразу після перевірки всіх ребер з меншими вагами.
20.58. Додайте в алгоритм Круськала реалізації двох функцій АТД, які заповнюють вектор, індексований іменами вершин, який поставляється клієнтською програмою. Цей вектор розбиває вершини на до таких кластерів, що жодне ребро з довжиною, більшою d, не з'єднує дві вершини з різних кластерів. Перша функція приймає в якості аргументу до і повертає d, а друга приймає в якості аргументу d і повертає к. Протестуйте отриману програму для різних до і d на випадкових евклідових графах з сусідніми зв'язками і на ґратчастих графах (див. Вправи 20.17 і 20.19) різних розмірів.
20.59. Розробіть реалізацію алгоритму Прима, заснованого на попередній сортування ребер.
20.60. Напишіть клієнтську програму, яка виконує динамічну графічну анімацію алгоритму Круськала (див. Вправу 20.52). Перевірте отриману програму на випадкових евклідових графах з сусідніми зв'язками і на ґратчастих графах (див. Вправи 20.17 і 20.19), використовуючи стільки крапок, скільки можна обробити за прийнятний час.