Наступне завдання відома в теорії графів під назвою завдання Штейнера: на площині задані п точок; потрібно з'єднати їх відрізками прямих таким чином, щоб сумарна довжина відрізків була найменшою.
В процесі пошуку рішення дозволено вводити нові точки; "Довжина" відрізка, що з'єднує дві задані точки, не обов'язково розуміється буквально геометрично - це може бути деяка кількісна оцінка "ціни" проходження з точки в точку з якоїсь ламаної лінії.
Можна дати наступну графову інтерпретацію завдання Штейнера. Дан неорієнтовані граф G0 = (V0. ∅) без ребер. Потрібно знайти незорієнтованості граф G = (V, Т) зі спеціальними властивостями.
Ми припускаємо, що кожному ребру будь-якого неориентированного графа, одержуваного в процесі виконання завдання, можна зіставити невід'ємне число, зване вагою цього ребра. При цьому, по-перше, шуканий граф G має бути неорієнтованим деревом, по-друге, його безліч вершин має включати безліч вершин вихідного графа, тобто V0 ⊆ V, і, по-третє, сума ваг його ребер повинна бути найменшою.
Вимога, щоб шуканий граф G був неорієнтованим деревом, викликано тим, що в ньому будь-яку пару вершин повинна з'єднувати єдина ланцюг, тому що в противному випадку граф не матиме найменшу суму ваг. Дійсно, якщо існують хоча б два ланцюги, що з'єднують якусь пару вершин, то вибирається та, сума ваг ребер якої менше. Білі ж припустити, що в ситуації, що розглядається є хоча б два ланцюги з однаковою вагою, то все одно для оптимального рішення вибирається якась одна ланцюг (і тоді оптимальне рішення не єдино).
Ефективних алгоритмів *, що дають точне рішення задачі Штейнера, не існує. Однак відомі ефективні алгоритми, що знаходять деякі наближення точного рішення. Одне з таких рішень дає алгоритм Краскала. Неорієнтовний (орієнтований) граф, у якого кожному ребру (дузі) зіставлено деяке дійсне число, називають зваженим або розмічені графом. Це число називають вагою або міткою ребра (дуги). Як правило, ми розглядаємо граф з натуральними мітками ребер (дуг).
* Алгоритм вважають ефективним, якщо складність алгоритму виражається функцією, обмеженої зверху деяким поліномом від параметра, що характеризує "обсяг" вихідних даних. Для завдання Штейнера цим параметром є число вершин графа G0.
Алгоритм Краскала обчислює для заданого зваженого неориентированного графа G кістяк з найменшою сумою ваг ребер - кістяк найменшої ваги. Істотна відмінність тільки що сформульованої задачі від завдання Штейнера (в її графовой постановці) полягає в тому, що в новому завданні безліч вершин при пошуку остовного дерева найменшої ваги не змінюється. Тому алгоритм Краскала і дає лише деяке наближення рішення задачі Штейнера.
При описі алгоритму будемо використовувати спосіб зберігання даних, званий чергою. Елементи даних у черзі упорядковуються за часом надходження. Елементи можна додавати в чергу і витягувати з черги. У кожен момент часу доступний тільки один елемент, який був поміщений в чергу раніше інших, - "голова" черги. При додаванні новий елемент поміщається в "хвіст" черги, тобто робота ведеться за звичайним для черги правилом - "першим прийшов - першим вийшов". Щоб витягти з черги певний елемент, не доступний в поточний момент, треба витягти всі раніше надійшли елементи, починаючи з "голови" черги.
Розглянемо алгоритм знаходження остовного дерева найменшої ваги (алгоритм Краскала). Нехай дано зв'язний неорієнтований граф G = (V, Е) з числовими невід'ємними вагами ребер. Вага ребра е позначимо φ (е).
В результаті роботи алгоритму отримаємо кістяк Т = (V, H) графа G, таке, що сума є найменшою.
Відсортуємо все ребра вихідного графа по зростанню ваг і сформуємо з них чергу так, щоб в "голові" черги знаходилося ребро з найменшою вагою, а в "хвості" - з найбільшим і ваги ребер не убуває від "голови" черги до "хвоста".
Метод полягає в "зшиванні" шуканого дерева з компонент остовного лісу. Спочатку остовно ліс являє собою безліч ізольованих вершин вихідного графа, тобто його безліч ребер порожньо. На першому кроці з черги витягується ребро найменшої ваги і додається до безлічі ребер вихідного дерева.
На наступних кроках алгоритму з черги витягується по одному ребру. Якщо це ребро з'єднує вершини, що належать різним компонентам поточного остовного лісу, то воно додається до поточного безлічі ребер шуканого дерева, а зазначені компоненти зливаються в одну. Інакше ребро відкидається. Процес повторюється до тих пір, поки число компонент остовного лісу не виявиться рівним 1. Можна показати, що ця компонента і буде шуканим остовне деревом найменшої ваги.
Переходимо до формального опису алгоритму.
- Безліч ребер Н шуканого остовного дерева вважаємо порожнім (H = ∅).
- Формуємо безліч VS = 1>. n >>, елементами якого є безлічі вершин, відповідних компонентів вихідного остовного лісу. Кожна така компонента складається з єдиної вершини.
- Сортуємо безліч ребер Е вихідного графа по зростанню ваг і формуємо чергу Q, елементами якої є ребра графа G.
- Якщо безліч VS містить більше одного елемента (тобто остовно ліс складається з декількох компонент) і черга Q не порожня, переходимо на крок 5, якщо інакше - на крок 7.
- Витягуємо з черги Q ребро е. Якщо кінці ребра е належать різним множинам вершин Vi і Vj з VS. то переходимо на крок 6, якщо інакше, то відкидаємо витягнуте ребро і повертаємося на крок 4.
- Об'єднуємо безлічі вершин Vi і Vj (вважаючи W = = Vi ∪ Vj), видаляємо безлічі Vi і Vj з безлічі VS і додаємо в VS безліч W. Додаємо ребро е в безліч Н. Повертаємося на крок 4.
- Припиняємо роботу. Безліч Н є безліч ребер отриманого остовного дерева.
Доведення коректності алгоритму Краскала, тобто доказ того факту, що видається алгоритмом ве дерево дійсно є остовне деревом найменшої ваги, ми не наводимо.
На рис. 5.19, а-д для неорієнтованого графа показана послідовність побудови остовного дерева найменшої ваги. Зауважимо, що результат роботи алгоритму в загальному випадку залежить від порядку проходження ребер однакової ваги в черзі. Припустимо, що після сортування першим в черзі знаходиться ребро 0. v1> з вагою 2.
Вихідний граф зображений на рис. 5.19, а. На рис. 5.19, б проілюстрований результат виконання першого кроку алгоритму. На рис. 5.19, в показаний результат додавання наступного ребра 1. v2> з вагою 2 з черги. На рис. 5.19, г наведено результат додавання ребра 0. v4> з вагою 3. Якщо наступним в черзі ребром буде 1. v4>, воно буде відкинуте. Подальший хід роботи алгоритму залежить від того, в якому порядку в черзі розміщені ребра 2. v3> і 3. v4> з вагами 4. Будь-яке з них може бути додано в безліч ребер остовного дерева, і на цьому алгоритм закінчить роботу. На рис. 5.19, д приведено кістяк, отримане після додавання ребра 3. v4>.
Відзначимо, що для наведеного графа обидва ребра з вагою 2 увійдуть в кістяк незалежно від порядку їх розташування в черзі після сортування, а ребро 1. v4 »не увійде ні в яке кістяк найменшої ваги.
Можна довести, що найбільш трудомістким кроком в алгоритмі Краскала є сортування ребер графа по зростанню ваг. Як ми вже знаємо, завдання сортування п елементів не можна вирішити швидше, ніж за час O (nlog2 n). Отже, складність алгоритму Краскала оцінюється числом O (| Е | log2 | Е |), де | Е | - потужність безлічі ребер графа. Оскільки справедливо нерівність | Е | log2 | E | ≤ | Е | 1. то алгоритм Краскала можна вважати ефективним.